An improved approximation algorithm for the covering 0-1 integer program

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.

Citation

to appear in department of Industrial Engineering and Economics Working Paper, Tokyo Institute of Technology.

Article

Download

View An improved approximation algorithm for the covering 0-1 integer program