"Department of Industrial Engineering and Economics Working Paper 2017-6" is now available

Department of Industrial Engineering and Economics issues the series of Working Paper to highlight our recent research activities.

The latest issue, 2017-6: Yotaro Takazawa, Shinji Mizuno, Tomonari Kitahara, An improved approximation algorithm for the covering 0-1 integer program.

Title of original paper

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

Author

Yotaro Takazawa, Shinji Mizuno, Tomonari Kitahara

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.

Following issues of Working Paper will appear as soon as available.

• Publications
• Department of Industrial Engineering and Economics Working Paper 2017-6