Optimization Online


A 2-approximation algorithm for the minimum knapsack problem with a forcing graph

Yotaro Takazawa (takazawa.y.ab***at***m.titech.ac.jp)
Shinji Mizuno (mizuno.s.ab***at***m.titech.ac.jp)

Abstract: Carnes and Shmoys (2015) presented a 2-approximation algorithm for the minimum knapsack problem. We extend their algorithm to the minimum knapsack problem with a forcing graph (MKPFG), which has a forcing constraint for each edge in the graph. The forcing constraint means that at least one item (vertex) of the edge must be packed in the knapsack. The problem is strongly NP-hard, since it includes the vertex cover problem as a special case. Generalizing the proposed algorithm, we also present an approximation algorithm for the covering integer program with 0-1 variables.

Keywords: Approximation algorithms, Minimum knapsack problem, Forc- ing graph, Covering integer program

Category 1: Combinatorial Optimization (Approximation Algorithms )

Citation: Working Paper No.2016-1, Department of Industrial Engineering and Economics, Tokyo Institute of Technology

Download: [PDF]

Entry Submitted: 06/29/2016
Entry Accepted: 06/29/2016
Entry Last Modified: 07/05/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society