TL;DR
This paper proves that the 30-year-old theoretical upper bounds for Integer Linear Program (ILP) proximity and sensitivity are tight. By constructing clever, non-negative ILP instances—including one based on the famous Petersen graph—the authors demonstrate that the distance between fractional and integer solutions can indeed reach the worst-case $\Delta^{\Theta(d)}$ scale, even in "natural" settings like Bin Packing.
What Problem Does This Paper Address?
In the world of optimization, Integer Linear Programs (ILPs) are notoriously difficult to solve. A common strategy is to solve the "fractional" version (the LP relaxation) and use it as a guide. Two critical measures define how well this works:
- Proximity: How far is the best integer solution from the best fractional solution?
- Sensitivity: If we slightly nudge the constraints (the right-hand side $b$), how much does the optimal integer solution jump?
In 1986, Cook et al. established that both measures are bounded by $\Delta^{\Theta(d)}$, where $\Delta$ is the largest entry in the constraint matrix and $d$ is the number of constraints. While these upper bounds have stood for decades, existing lower bounds (examples showing the bounds are "tight") were often unsatisfying—they relied on negative numbers, fractional constraints, or only worked for tiny values of $\Delta$. This paper asks: do these extreme gaps actually occur in "polytopish" ILPs—the kind that arise naturally in combinatorial optimization problems like Bin Packing?
Methods
The authors prove tightness by constructing two specific types of ILP instances that force the solution to explode geometrically.
- Sensitivity Construction: They design a "staircase" matrix where each row $i$ is linked to row $i+1$ by a factor of $\Delta$. A change of just $1$ in the first constraint ripples through the system, forcing the variables in the optimal solution to shift by powers of $\Delta$ (e.g., $\Delta, \Delta^2, \Delta^3...$).
- Proximity Construction: This is the paper's most creative leap. They use the Petersen graph to create a structural gap.
By mapping the graph's edges to constraints and its perfect matchings to columns, they create a scenario where a fractional solution can elegantly use "half" of each matching to satisfy constraints perfectly. However, an integer solution is forced to either avoid matchings entirely or pick one and then use a massive number of "slack" variables to fix the resulting imbalances, creating a huge distance between the two optima.
Datasets
Not discussed in the paper. As a theoretical work in computational complexity and discrete geometry, it relies on mathematical proofs and constructive examples rather than empirical datasets.
Key Insights and Ideas
- Non-negativity Matters: Unlike previous lower bounds, these constructions use only non-negative entries. This is crucial because many algorithmic problems (like scheduling or packing) naturally have non-negative constraints.
- The Petersen Graph as a "Gap Generator": The authors exploit the fact that every edge in a Petersen graph belongs to exactly two perfect matchings, and any two matchings share exactly one edge. This specific symmetry is what makes the fractional solution "cheap" and the integer solution "expensive."
- Bin Packing Connection: The authors show that their hard instances are actually subsets of the "Configuration ILP" for the Bin Packing problem. This implies that the standard proximity bounds used to analyze Bin Packing algorithms cannot be improved without specifically accounting for the objective function (minimizing the number of bins).
Key Results
- Tightness Confirmed: The paper provides the first lower bounds of $\Delta^{\Theta(d)}$ for proximity and sensitivity using non-negative, integral matrices and right-hand sides.
- Theorem 1 (Sensitivity): For even $d$, there exists a matrix where changing the right-hand side by 1 results in a solution shift of at least $\Delta^{\Theta(d)}$.
- Theorem 2 (Proximity): For odd $d$, there exists an ILP where the optimal integer solution is at least $\Delta^{\Theta(d)}$ away from the optimal fractional solution.
- Polytopish Nature: All constructed instances are "polytopish," meaning they represent valid points within a defined polytope, making them highly relevant to real-world algorithmic design.
Limitations and Future Work
The authors note that while these bounds are tight for general ILPs, they might be pessimistic for specific problems if the objective function is taken into account. For example, in the Bin Packing problem, the objective is specifically to minimize the sum of variables ($\min \|x\|_1$). The authors suggest that future research could investigate whether this specific objective function allows for smaller proximity or sensitivity bounds than the general $\Delta^{\Theta(d)}$ worst-case.
Summary updated