Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10107-012-0518-y | Mathematical Programming |
Keywords | DocType | Volume |
complexity,matrices,frobenius problem,polyhedra | Journal | 141 |
Issue | ISSN | Citations |
1-2 | 1436-4646 | 3 |
PageRank | References | Authors |
0.43 | 14 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Friedrich Eisenbrand | 1 | 726 | 53.74 |
| nicolai haehnle | 2 | 3 | 0.43 |
| Dömötör Pálvölgyi | 3 | 15 | 3.79 |
| gennady shmonin | 4 | 65 | 3.48 |