combinatorics
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: a seventeen-terminal common-point interval instance certifies $$ C\ \ge\ \frac{1282494797984843521}{10^{18}}=1.28249\ldots $$ Upper bounds: the paper proves the first unconditional ceiling below 2, but for the codimension-two case only, at complement mass $q=2$. The record cells lie outside it, the $k=17$ instance having $q=11$, so that ceiling does not bound the record ladder. Two figures are conjectures rather than results: $4/3$ as the supremum of critical constants over common-point cells, approached but not attained and not an extrapolation from the ladder (Conjecture 1.1, Theorem 5.1), and $2$ for the universal constant itself (Conjecture 1.2). The proved gap remains $[1.28249\ldots,\ 2]$.
Temporal state
No reconciled state yet.
Append-only history
Record lower bound only. The sub-2 ceiling is the codimension-two case and does not bound the record ladder (k=17 has complement mass 11). 4/3 and 2 are conjectures; the proved gap is [1.28249, 2].
Research memory
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: a seventeen-terminal common-point interval instance certifies $$ C\ \ge\ \frac{1282494797984843521}{10^{18}}=1.28249\ldots $$ Upper bounds: the paper proves the first unconditional ceiling below 2, but for the codimension-two case only, at complement mass $q=2$. The record cells lie outside it, the $k=17$ instance having $q=11$, so that ceiling does not bound the record ladder. Two figures are conjectures rather than results: $4/3$ as the supremum of critical constants over common-point cells, approached but not attained and not an extrapolation from the ladder (Conjecture 1.1, Theorem 5.1), and $2$ for the universal constant itself (Conjecture 1.2). The proved gap remains $[1.28249\ldots,\ 2]$.
Record lower bound only. The sub-2 ceiling is the codimension-two case and does not bound the record ladder (k=17 has complement mass 11). 4/3 and 2 are conjectures; the proved gap is [1.28249, 2].
Evidence graph
derived from · problem · open
depends on · problem · claimed