An approximation algorithm for the partial covering 0-1 integer program
Yotaro Takazawa (takazawa.y.abm.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.
Entry Submitted: 01/07/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|