Source-linked AI summary
Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma
Friedrich Eisenbrand, Robert Weismantel
TL;DR
The paper studies integer programs and improves prior algorithmic and proximity bounds using the Steinitz lemma. It obtains bounds independent of the number of variables and applies them to faster dynamic programs, including bounded-variable and knapsack settings.
Problem
Papadimitriou’s algorithm had running time (m·Δ)^{O(m^2)} and required the entries of b to be bounded by Δ, leaving an open improvement problem.
Method
The paper uses the Steinitz lemma to derive proximity bounds between optimal linear-programming and integer solutions, then incorporates those bounds into dynamic programming algorithms.
Results
The resulting proximity bound is independent of n, improves the standard-form distance bound by a factor of n^2 for fixed m, and saves a factor of n in the cited algorithmic cases.
Takeaways & Limitations
The bounds support faster algorithms for integer programs, including running time O(m·Δ)^m·∥b∥1·n when A has only non-negative entries.
Takeaways & Limitations
The bounded-variable proximity setting assumes 0≤x≤u and that every entry of A has absolute value at most Δ.
Abstract
from arXiv · showhide
We consider integer programming problems in standard form $\max \{c^Tx : Ax = b, \, x\geq 0, \, x \in Z^n\}$ where $A \in Z^{m \times n}$, $b \in Z^m$ and $c \in Z^n$. We show that such an integer program can be solved in time $(m Δ)^{O(m)} \cdot \|b\|_\infty^2$, 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\cdot Δ)^{O(m^2)}$, 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^m$ 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 $\ell_1$-distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded by $m \cdot (2\,m \cdot Δ+1)^m$. 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.
1 Introduction
The paper develops structural and algorithmic results for standard-form integer programs using the Steinitz lemma, improving prior running-time and proximity bounds. It also applies these results to knapsack problems and connects them to ongoing work on integer programming and discrepancy.
- Contributions of this paper: The paper studies standard-form integer programs and uses the Steinitz lemma to obtain new structural and algorithmic results.Integer programs in inequality form can be transformed into standard form; the paper focuses on the latter representation.
- Contributions of this paper: (m·Δ)^{O(m)} running time improves on Papadimitriou’s (m·Δ)^{Ω(m^2)} bound when only A is entrywise bounded by Δ.Papadimitriou’s setting also bounds the entries of b by Δ, whereas the new result requires this only for A and addresses an open problem.
- Contributions of this paper: An ℓ1 proximity bound independent of n improves the standard-form comparison bound by a factor of n^2 for fixed m.The prior bound is stated as ∥z*−x*∥1 ≤ n^2·(√m·Δ)^m, while the new bound is independent of n.
- Contributions of this paper: The proximity result also bounds the absolute integrality gap by ∥c∥∞·O(m)^{m+1}·O(Δ)^m.This generalizes a recent one-row result for m = 1.
- Applications and related work: For knapsack problems, the resulting algorithms improve the best previous bounds by a factor of n.The paper applies the structural results to obtain improved algorithmic results for unbounded and bounded knapsack variants.
- The Steinitz lemma: The Steinitz lemma orders zero-sum vectors in a bounded norm so that every partial sum remains bounded by a dimension-dependent constant.For the ℓ∞-norm, the illustrated reordering keeps partial sums bounded by 2; the paper uses the lemma as the basis for its proofs.
2 A faster dynamic program
The paper builds a dynamic program from a Steinitz-type lemma by representing feasible solutions as walks in a bounded-state digraph. This yields feasibility and optimization algorithms whose running times depend on m, Δ, b, and n, with stronger bounds in special cases.
- State-space construction: The Steinitz-type lemma bounds partial sums, allowing feasible solutions to be represented as walks through a finite set S of integer states.The states lie near the line segment from 0 to b, with |S| bounded by (4m · Δ+1)^m · ∥b∥1.
- State-space construction: (4m · Δ+1)^m · ∥b∥1 bounds the number of vertices, while the number of arcs is at most |S|·n.Feasibility becomes an unweighted single-source shortest-path problem solvable by breadth-first search.
- Feasibility: O(m · Δ)^m · ∥b∥1 · n computes a feasible solution or certifies that none exists.This is the running time stated in Theorem 2.
- Optimization: Longest paths in the weighted digraph correspond to optimal integer solutions, while reachable positive cycles characterize unboundedness.The arc weight is the objective coefficient associated with the corresponding column of A.
- Optimization: (m · Δ)^O(m) · ∥b∥2 is the running-time bound for standard-form integer programming without variable upper bounds.Here Δ bounds the absolute values of entries of A; when A has only nonnegative entries, the bound improves to O(m·Δ)^m·∥b∥1·n.
- Special cases: n · O(m · Δ)^2m applies when both A and b are bounded by Δ, improving to n · O(m · Δ)^m when the digraph has no cycles.The acyclic case includes integer programs whose matrix A has only nonnegative entries.
3 Proximity in the ℓ1-norm
The paper develops an ℓ1 proximity bound between optimal LP and integer solutions for bounded-variable integer programs. Its proof excludes removable cycles and applies the Steinitz lemma to obtain a bound independent of the number of variables.
- Setting: The bounded-variable setting considers max{c^T x : Ax = b, 0 ≤ x ≤ u, x ∈ Z^n}, with A entries bounded in absolute value by Δ.The proximity result compares an optimal LP vertex with a closest optimal integer solution.
- Cycle elimination: A cycle of z*−x* preserves integer feasibility, preserves LP feasibility in the opposite direction, and has nonpositive objective value.These properties follow from Ay = 0, the variable bounds, and LP optimality.
- Cycle elimination: Choosing an optimal integer solution minimizing ∥z*−x*∥1 eliminates all cycles of z*−x*.Any such cycle would produce another optimal integer solution with strictly smaller ℓ1-distance.
- Proximity bound: Repeated partial sums would partition the Steinitz sequence into zero-sum pieces and create a forbidden cycle, so the sequence length is bounded by m times the number of short integer vectors.This counting argument yields the stated proximity bound.
- Knapsack consequence: The proximity bound also directly bounds the absolute integrality gap through c^T(x*−z*).The paper states that this follows by applying Theorem 7.
- Knapsack consequence: For one-row unbounded knapsack, the argument gives ∥z*−x*∥1 ≤ 2Δ, matching the cited asymptotic bound exactly.The one-dimensional case permits choosing the first Steinitz vector specially.
4 Algorithmic implications
The paper uses proximity bounds to reduce bounded integer programs to dynamic programs on acyclic graphs. Binary decompositions control graph size, and the approach yields improved knapsack algorithms.
- Integer-programming algorithm: An optimal basic LP solution is used as a reference, after which proximity bounds restrict the integer correction to bounded ℓ1-distance.The correction is represented by y = z − ⌊x*⌋ with coordinate bounds derived from the proximity bound.
- Integer-programming algorithm: The correction problem is encoded as a longest-path problem in an acyclic graph whose nodes track partial constraint sums.The graph contains a start node, a target node, and copies of a bounded set U; feasible arcs correspond to integer variable choices.
- Graph compression: Binary representations replace interval transitions with O(log2(U +L)) pieces, reducing each node’s out-degree to at most two.This construction preserves representability of every integer in the interval while making the dynamic program sparser.
- Graph compression: Theorem 8 states that the bounded-variable integer program can be solved under the assumption that every entry of A has absolute value at most Δ.The resulting graph can be solved by longest-path computation because it is acyclic.
- Knapsack applications: For bounded knapsack, the proximity-based method improves the prior O(n^2·Δ^2a) running time by saving a factor of n.The paper also derives an O(n^2·Δ^2) algorithm in the one-row case and states a corresponding unbounded-knapsack theorem.