1.28249... Lower Bound and Partial Upper Bounds for Cost-Preserving Single-Source Unsplittable Flows

For a single-source unsplittable flow, find the optimal universal additive constant $C$ s.t. every feasible fractional flow $x$ with arc costs $c$ should admit an unsplittable routing $y$ with $c^\top y \le c^\top x$ and $y_a \le x_a + C \cdot d_{\max}$ on every arc. Goemans conjectured $C=1$ ; this was disproved in July 2026 by a separate seven-vertex counterexample with critical constant $16/15$ (see the Dinitz–Garg–Goemans entry), leaving the optimal $C$ open. Lower bound: we present a seventeen-terminal common-point interval instance that certifies $C\ \ge\ \frac{1282494797984843521}{10^{18}}=1.28249\ldots$ Upper bounds: we prove the first unconditional upper bound below 2 for a nontrivial family of extremal cells, representing the class as a weighted two-permutation prefix system. We also prove additional structural results on the limits of techniques used for the lower bound. The ceilings apply to the common-point / two-order class from which the lower bounds are drawn, not to the universal constant $C$ itself.

Result: Proved (Record lower bound plus class-restricted ceilings; the existence and exact value of a finite universal constant remain open)
Status: Partial result
AI contribution: AI co-developed
Method: Construction
Field: Combinatorics
Posed by: Dinitz, Garg, Goemans
Year posed: 1999
Years open: 27y
Solved: 2026-07-31
Model: GPT-5.6 Sol, Claude Fable 5, Claude Opus 5
Vendor: OpenAI, Anthropic
Collaborators: Sergey Nikolenko
Verification: Site-confirmed
Publication: Preprint
Significance: 15 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What the AI did

GPT-5.6 Sol, Claude Fable 5 and Claude Opus 5 carried out the search for constructions, symbolic envelope derivations, proofs, and the exact-verifier development; the human author framed the program, directed the search, set the claim scope, and verified all results independently by hand.

Verification

The k=17 lower bound is a finite certificate: the verifier rebuilds the 67-arc instance from raw interval data, rediscovers all paths by DFS, and enumerates all 2^17 routings in exact rational arithmetic. Re-run by the site from a clean clone on 2026-08-01; the exact constant, 15 minimizers, and 18-atom hull certificate reproduce. The deletion-star ceiling theorems are conventional proofs in an unreviewed preprint, checked by the author only — no independent expert review, no formalization. Tier reflects the site's confirmation of the certificate; the structural results remain unreviewed.

Sources

Unsplittable flows repository

Submitted by BraveDingo215

Discussion3

Rasmus Lindahl01 Aug 2026· edited

Feel free to discuss any entry values that might be wrong here. Also thank you for the submission :)

BraveDingo21501 Aug 2026· edited

Thanks for the quick turnaround! Just wanted to add what I forgot to mention in the description: the limit for this class of examples is $\tfrac 43$ as the number of terminals in the graph goes to $\infty$ . So with a huge computation, we could probably get to $\tfrac 43 - \epsilon$ ; $1.28249...$ is a specific graph with $17$ terminals.

Rasmus Lindahl01 Aug 2026

Thanks, that's really useful context! So 1.28249 and so on is just where the explicit k=17 certificate lands, and the family should approach 4/3 as the number of terminals grows. Is the 4/3 limit established somewhere in the preprint (I could only find the 3/2 ceiling for the class), or is it numerical/expected for now? Happy to add it to the entry either way, I just want to label it correctly as proved versus conjectured. And if you ever certify a larger instance, the entry can track the new record constant.