Loading...
conference paper
Testing additive integrality gaps
2010
21st ACM-SIAM Symposium on Discrete Algorithms (SODA10)
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.
Loading...
Name
eisenbrandf-gaps.pdf
Access type
openaccess
Size
153.75 KB
Format
Adobe PDF
Checksum (MD5)
022c68bd6c71ab883653260d48e1d9ff