Optimization Online


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

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

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.

Download: [PDF]

Entry Submitted: 08/06/2017
Entry Accepted: 08/24/2017
Entry Last Modified: 08/06/2017

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