Approximation algorithms for the covering-type k-violation linear program

Yotaro Takazawa (takazawa.y.abm.titech.ac.jp)
Shinji Mizuno (mizuno.s.abm.titech.ac.jp)
Tomonari Kitahara (kitahara.t.abm.titech.ac.jp)

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 using the LP-relaxation as a lower bound of the optimal value.

Keywords: Approximation algorithms, Mixed integer program, k-violation linear program, Linear relaxation, Rounding algorithm

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: to appear in department of Industrial Engineering and Economics Working Paper, Tokyo Institute of Technology.

Download: [PDF]

Entry Submitted: 11/01/2017
Entry Accepted: 12/31/2018
Entry Last Modified: 01/06/2018

Modify/Update this entry