文献

J-GLOBAL ID：201702221360359099   整理番号：17A0441801

強制グラフを伴う最小ナップサック問題のための2-近似アルゴリズム

A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH

著者 (2件)： Takazawa Yotaro (Tokyo Institute of Technology) ,  Mizuno Shinji (Tokyo Institute of Technology)
資料名： Journal of the Operations Research Society of Japan  (Journal of the Operations Research Society of Japan)
巻： 60  号： 1  ページ： 15-23(J-STAGE)  発行年： 2017年 
JST資料番号： G0402A  ISSN： 0453-4514  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： CarnesとShmoys[2]は最小ナップサック問題に対する2-近似アルゴリズムを提示した。本稿は同アルゴリズムを強制グラフを伴う最小ナップサック問題(MKPFG)に拡張するが,それはグラフの各エッジに対する強制制約条件を有する。強制制約条件とは,エッジの少なくとも一つの項目(バーテックス)はナップサックに詰められていなければならないことを意味する。同問題は特別のケースとしてバーテックス被服問題を含むので,強NP困難である。提案されたアルゴリズムを一般化し,0-1変数を持つ整数計画を被服する近似アルゴリズムをも提示した。(翻訳著者抄録)

シソーラス用語： *ナップサック問題 ,  *計算機アルゴリズム ,  頂点 ,  問題 ,  被覆問題 ,  *組合せ最適化問題 ,  整数計画法
準シソーラス用語： NP困難問題 ,  バーテックス ,  *近似アルゴリズム

著者キーワード (5件)： Combinatorial optimization ,  approximation algorithms ,  minimum knapsack problem ,  forcing graph ,  covering integer program

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

引用文献 (15件)：

• [1] R. Bar-Yehuda and S. Even: A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2 (1981), 198-203.
• [2] T. Carnes and D. Shmoys: Primal-dual schema for capacitated covering problems. Mathematical Programming, 153 (2015), 289-308.
• [3] R.D. Carr, L. Fleischer, V.J. Leung, and C.A. Phillips: Strengthening integrality gaps for capacitated network design and covering problems. Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (2000), 106-115.
• [4] A. Darmann, U. Pferschy, J. Schauer, and G.J. Woeginger: Paths, trees and matchings under disjunctive constraints. Discrete Applied Mathematics, 159 (2011), 1726-1735.
• [5] I. Dinur and S. Safra: On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162 (2005), 439-485.

タイトルに関連する用語 (4件)： 強制 ,  グラフ ,  ナップサック問題 ,  近似アルゴリズム