Loading...
Please wait, while we are loading the content...
Similar Documents
Distances to lattice points in knapsack polyhedra
| Content Provider | Semantic Scholar |
|---|---|
| Author | Aliev, Iskander Henk, Martin Oertel, Timm |
| Copyright Year | 2018 |
| Abstract | We give an optimal upper bound for the $$\ell _{\infty }$$ℓ∞-distance from a vertex of a knapsack polyhedron to its nearest feasible lattice point. In a randomised setting, we show that the upper bound can be significantly improved on average. As a corollary, we obtain an optimal upper bound for the additive integrality gap of integer knapsack problems and show that the integrality gap of a “typical” knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario. We also prove that, in a generic case, the integer programming gap admits a natural optimal lower bound. |
| Starting Page | 1 |
| Ending Page | 24 |
| Page Count | 24 |
| File Format | PDF HTM / HTML |
| DOI | 10.1007/s10107-019-01392-1 |
| Alternate Webpage(s) | http://orca.cf.ac.uk/121278/7/Aliev_et_al-2019-Mathematical_Programming_.pdf |
| Alternate Webpage(s) | https://www.cirm-math.fr/ProgWeebly/Renc1860/Aliev.pdf |
| Alternate Webpage(s) | https://arxiv.org/pdf/1805.04592v1.pdf |
| Alternate Webpage(s) | https://doi.org/10.1007/s10107-019-01392-1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
