Computational study of the conjectured limiting ratio 2d for the iterative rounding algorithm on hard instances discovered via Co-FunSearch. Based on Nikoleit et al., arXiv:2601.16849 (Jan 2026).
| k | n | APX | OPT (LP) | APX/n |
|---|---|---|---|---|
| 2 | 6 | 6.0 | -2.0 | 1.00 |
| 3 | 14 | 25.0 | -4.0 | 1.79 |
| 4 | 30 | 113.0 | -8.0 | 3.77 |
| 5 | 62 | 481.0 | -16.0 | 7.76 |
| d | k | n | APX | OPT (LP) | Predicted 2d |
|---|---|---|---|---|---|
| 1 | 2 | 6 | 6.0 | -2.0 | 2 |
| 1 | 3 | 14 | 25.0 | -4.0 | 2 |
| 1 | 4 | 30 | 113.0 | -8.0 | 2 |
| 1 | 5 | 62 | 481.0 | -16.0 | 2 |
| 2 | 2 | 6 | 8.0 | -4.0 | 4 |
| 2 | 3 | 14 | 29.0 | -6.0 | 4 |
| 3 | 2 | 12 | 19.0 | -4.0 | 6 |
| d | k | n | APX | OPT (exact) | OPT (LP) | Ratio (exact) |
|---|---|---|---|---|---|---|
| 1 | 2 | 6 | 6.0 | 4.0 | -2.0 | 1.5 |
| 1 | 3 | 14 | 25.0 | -4.0 | -4.0 | --- |
| 2 | 2 | 6 | 8.0 | 8.0 | -4.0 | 1.0 |
Decompose the objective into d independent coordinate contributions. Each coordinate contributes ratio approaching 2: coordinate 1 via Lorieau's 1D analysis, auxiliary coordinates via the 4 vs 2 coefficient asymmetry. Total: 2 + (d-1) x 2 = 2d. Challenge: proving LP relaxation does not couple coordinates to improve fractional solution.
Track dual feasible solutions (shadow prices) across rounding steps to lower-bound OPT at every step. The geometric progression u_i = 2^k(1 - 2^{-i}) creates self-similar dual structure. Most rigorous but technically demanding due to O(nd) dual constraints.
Exploit the recursive structure: instance at parameter k embeds instance at k-1. Derive recurrences APX(k,d) = f(APX(k-1,d), k, d) and OPT(k,d) = g(OPT(k-1,d), k, d). Most constructive approach but fragile under tie-breaking rule changes.
Nikoleit, Allouah, Kleer, Marchetti-Bowick, Talgam-Cohen. The Art of Being Difficult: Combining Human and AI Strengths to Find Adversarial Instances for Heuristics. arXiv:2601.16849, January 2026. [arXiv]