An improved approximation algorithm for the covering 0-1 integer program
Abstract: We present an improved approximation algorithm for the covering 0-1 integer program (CIP), a well-known problem as a natural generalization of the set cover problem. Our algorithm uses a primal-dual algorithm for CIP by Fujito (2004) as a subroutine and achieves an approximation ratio of (f- (f-1)/m) when m is greater than or equal to 2, where m is the number of the constraints and f is the maximum number of non-zero entries in the constraints. In addition, when m=1 our algorithm can be regarded as a PTAS. These results improve the previously known approximation ratio f.
Keywords: Approximation algorithms, Covering integer program, Primal-dual method
Category 1: Combinatorial Optimization (Approximation Algorithms )
Citation: to appear in department of Industrial Engineering and Economics Working Paper, Tokyo Institute of Technology.
Entry Submitted: 08/06/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|