Paper Info
Title
An approximation algorithm for the partial covering 0–1 integer program
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).
Year
DOI
Venue
2020
10.1016/j.dam.2017.08.024
Discrete Applied Mathematics
Keywords
Field
DocType
Approximation algorithms,Partial covering 0–1 integer program,Primal–dual method
Integer,Set cover problem,Discrete mathematics,Approximation algorithm,Combinatorics,Mathematics
Journal
Volume
ISSN
Citations 
275
0166-218X
0
PageRank 
References 
Authors
0.34
6
3
Name
Order
Citations
PageRank
Yotaro Takazawa100.68
Shinji Mizuno2792153.37
Tomonari Kitahara3246.61