  


A 2approximation algorithm for the minimum knapsack problem with a forcing graph
Yotaro Takazawa (takazawa.y.abm.titech.ac.jp) Abstract: Carnes and Shmoys (2015) presented a 2approximation 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 NPhard, 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 01 variables. Keywords: Approximation algorithms, Minimum knapsack problem, Forc ing graph, Covering integer program Category 1: Combinatorial Optimization (Approximation Algorithms ) Citation: Working Paper No.20161, Department of Industrial Engineering and Economics, Tokyo Institute of Technology Download: [PDF] Entry Submitted: 06/29/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  