Infoscience

Similar records
Conference paper

Testing additive integrality gaps

Eisenbrand, Friedrich; Hähnle, Nicolai; Pálvölgyi, Dömötör; Shmonin, Gennady
  • Presented at: 21st ACM-SIAM Symposium on Discrete Algorithms, Austin, Texas, January 17-19, 2010
  • Accepted in: 21st ACM-SIAM Symposium on Discrete Algorithms (SODA10), p. 1227-1234
  • : , 2010

We consider the problem of testing whether the maximum 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.

Keywords: Integer Decomposition ; Frobenius Problem ; Fixed Dimension ; Complexity ; Polyhedra ; Matrices

Reference

Record created on 2009-09-04, modified on 2012-03-27

Fulltext

Contacts

EPFL authors