Papers › Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma
Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma
Friedrich Eisenbrand, Robert Weismantel
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We consider integer programming problems in standard form max{cᵀx : Ax = b, x≥0, x ∈Zⁿ} where A ∈Z^(m ×n), b ∈Zᵐ and c ∈Zⁿ. We show that such an integer program can be solved in time (m Δ)ᴼ⁽ᵐ⁾ ·b_∞², where Δ is an upper bound on each absolute value of an entry in A. This improves upon the longstanding best bound of Papadimitriou (1981) of (m·Δ)^(O(m²)), where in addition, the absolute values of the entries of b also need to be bounded by Δ. Our result relies on a lemma of Steinitz that states that a set of vectors in Rᵐ that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by m. We also use the Steinitz lemma to show that the ℓ₁-distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded by m ·(2 m ·Δ+1)ᵐ. Here Δ is again an upper bound on the absolute values of the entries of A. The novel strength of our bound is that it is independent of n. We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections