Paper Info
Title
Approximation algorithms for the covering-type k-violation linear program
Abstract
We study the covering-type k-violation linear program where at most k of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we present a simple $$(k+1)$$ -approximation algorithm using a natural LP relaxation. We also show that the integrality gap of the LP relaxation is $$k+1$$ . This implies we can not get better approximation algorithms when we use the LP-relaxation as a lower bound of the optimal value.
Year
DOI
Venue
2019
10.1007/s11590-019-01425-w
Optimization Letters
Keywords
Field
DocType
Approximation algorithms, Mixed integer program, k-violation linear program, Linear relaxation, Rounding algorithm
Integer,Approximation algorithm,Discrete mathematics,Mathematical analysis,Upper and lower bounds,Linear programming,Linear programming relaxation,Mathematics
Journal
Volume
Issue
ISSN
13
7
1862-4472
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Yotaro Takazawa100.68
Shinji Mizuno2792153.37
Tomonari Kitahara3246.61