Art

J-GLOBAL ID：201702221360359099   Reference number：17A0441801

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

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

Author (2)： Takazawa Yotaro (Tokyo Institute of Technology) ,  Mizuno Shinji (Tokyo Institute of Technology)
Material： Journal of the Operations Research Society of Japan  (日本オペレーションズ・リサーチ学会論文誌)
Volume： 60  Issue： 1  Page： 15-23(J-STAGE)  Publication year： 2017 
JST Material Number： G0402A  ISSN： 0453-4514  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *knapsack problem ,  *computer algorithm ,  vertex ,  problem ,  covering problem ,  *combinatorial optimization problem ,  integer programming ,  *approximate algorithm
Semi thesaurus term： NP-hard problem ,  vertex

Author keywords (5)： Combinatorial optimization ,  approximation algorithms ,  minimum knapsack problem ,  forcing graph ,  covering integer program

JST classification (1)： Mathematical programmings  (KA03030M)

Reference (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.

Terms in the title (4)： 強制 ,  グラフ ,  ナップサック問題 ,  近似アルゴリズム