Testing additive integrality gaps

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomial time if the number of constraints is fixed. It turns out that this generalization is NP-hard even if the number of constraints is fixed. However, if, in addition, the objective is the all-one vector, then one can test in polynomial time whether the additive gap is bounded by a constant.


Published in:
Mathematical Programming, 141, 1-2, 257-271
Year:
2013
Publisher:
New York, Springer
ISSN:
0025-5610
Laboratories:




 Record created 2013-11-04, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)