文献

J-GLOBAL ID：201602281343813343   整理番号：16A0565793

互換性のある二部グラフを伴う多重ナップサック問題

THE MULTIPLE KNAPSACK PROBLEM WITH COMPATIBLE BIPARTITE GRAPHS

著者 (3件)： LI Jianping (Yunnan Univ., Kunming, CHN) ,  LI Weidong (Yunnan Univ., Kunming, CHN) ,  WANG Hao (Yunnan Univ., Kunming, CHN)
資料名： IET Conference Publications  (IET Conference Publications)
巻： 673  ページ： 86-92  発行年： 2015年 
JST資料番号： B0665A  ISSN： 0537-9989  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： イギリス (GBR)  言語： 英語 (EN)

抄録/ポイント： 標記の多重ナップサック問題の変形版について考察した。この変形版では,2つの品目の対応する頂点が与えられた互換二部グラフにおいて隣接している場合に限って,それらを同一のナップサックにパックできる。ここでは,二つの異なる目標の下で,同問題が強いNP困難性を持つことを証明した。また,いくつかの1/2近似アルゴリズムを示したほか,全てのナップサックが同一の容量を持つ特別な場合に関して,2つの最適アルゴリズムを与えた。

シソーラス用語： *ナップサック問題 ,  部分グラフ ,  計算機アルゴリズム ,  アルゴリズム ,  *0-1整数計画法 ,  NP困難
準シソーラス用語： NP困難性 ,  二部グラフ ,  近似アルゴリズム ,  最適化アルゴリズム ,  多項式時間アルゴリズム

分類 (1件)： 数理計画法  (KA03030M)

タイトルに関連する用語 (4件)： 互換性 ,  二部グラフ ,  多重 ,  ナップサック問題