Metadata only
Date
2022Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
Consider a linear program of the form max{c x : Ax ≤ b}, where A is an m × n integral matrix. In 1986 Cook, Gerards, Schrijver, and Tardos proved that, given an optimal solution x∗, if an optimal integral solution z∗ exists, then it may be chosen such that x∗ − z∗ ∞ < nΔ, where Δ is the largest magnitude of any subdeterminant of A. Since then an open question has been to improve this bound, assuming that b is integral valued too. In this manuscript we show that nΔ can be replaced with n/2 · Δ whenever n ≥ 2 and x∗ is a vertex. We also show that, in certain circumstances, the factor n can be removed entirely Show more
Publication status
publishedExternal links
Book title
Integer Programming and Combinatorial OptimizationJournal / series
Lecture Notes in Computer ScienceVolume
Pages / Article No.
Publisher
SpringerEvent
Organisational unit
03873 - Weismantel, Robert / Weismantel, Robert
More
Show all metadata
ETH Bibliography
yes
Altmetrics