Optimization Online


An approximation algorithm for the partial 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: The partial covering 0-1 integer program (PCIP) is a relaxed problem of the covering 0-1 integer program (CIP) such that some fixed number of constraints may not be satisfied. This type of relaxation is also discussed in the partial set multi-cover problem (PSMCP) and the partial set cover problem (PSCP). In this paper, we propose an approximation algorithm for PCIP by extending an approximation algorithm for PSCP by Gandhi et al. (2004).

Keywords: Approximation algorithms, Partial covering 0--1 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: 01/07/2017
Entry Accepted: 01/07/2017
Entry Last Modified: 07/03/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