combinatorics

1.17353 planar lower bound and exact local envelopes for cost-preserving single-source unsplittable flow

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$ on every arc. We provide several new results on $C$: (1) record lower bound for planar instances (against known ceiling 2): $$C \ge \frac{58676765987259}{50000000000000} = 1.17353531974518;$$ (2) local envelope ladder (proved): $E(2) = 1$, $E(3) = 9/8$, $E(4) = (299 - 41\cdot\sqrt{41})/32 = 1.13974707\ldots$, attained by the counterexamples from our previous work; record constants of our previous work are now exact local envelopes of the general theory; (3) global results: every exact-two-path instance with rows touching at most three terminals satisfies $C \le 2$ (first unconditional constant for an unbounded class); interaction arity m gives $\lceil\lfloor 3m/2\rfloor /2\rceil \cdot D$; (4) classes closed exactly: out-trees 0; two-layer hubs 1; outerplanar two-exit interval spines 1 (sharp); series-parallel $\le 1$; (5) band merger constant $K^* \ge 2.5652\ldots$ (twice the general lower bound $1.2826\ldots$).

15Significance / 100
1Frontier events
0Verification tasks
0Recorded attempts

Temporal state

Current frontier

No reconciled state yet.

Append-only history

Frontier timeline

combinatoricsAug 13, 2026Significance 15/100Registry: site confirmed

1.17353 planar lower bound and exact local envelopes for cost-preserving single-source unsplittable flow

Prior state unknownproved

Part III of a series, and the first unconditional positive results in it. Settled exactly: the local envelope ladder $E(2)=1$, $E(3)=9/8$ and $E(4)=(299-41\sqrt{41})/32=1.13974707\ldots$, which recasts the earlier record constants as exact envelopes of the general theory rather than isolated instances, plus exact constants for four classes - out-trees 0, two-layer hubs 1, outerplanar two-exit interval spines 1 (sh…

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Research memory

Claims and attempts

Scoped claims

Source authenticated

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$ on every arc. We provide several new results on $C$: (1) record lower bound for planar instances (against known ceiling 2): $$C \ge \frac{58676765987259}{50000000000000} = 1.17353531974518;$$ (2) local envelope ladder (proved): $E(2) = 1$, $E(3) = 9/8$, $E(4) = (299 - 41\cdot\sqrt{41})/32 = 1.13974707\ldots$, attained by the counterexamples from our previous work; record constants of our previous work are now exact local envelopes of the general theory; (3) global results: every exact-two-path instance with rows touching at most three terminals satisfies $C \le 2$ (first unconditional constant for an unbounded class); interaction arity m gives $\lceil\lfloor 3m/2\rfloor /2\rceil \cdot D$; (4) classes closed exactly: out-trees 0; two-layer hubs 1; outerplanar two-exit interval spines 1 (sharp); series-parallel $\le 1$; (5) band merger constant $K^* \ge 2.5652\ldots$ (twice the general lower bound $1.2826\ldots$).

Part III of a series, and the first unconditional positive results in it. Settled exactly: the local envelope ladder $E(2)=1$, $E(3)=9/8$ and $E(4)=(299-41\sqrt{41})/32=1.13974707\ldots$, which recasts the earlier record constants as exact envelopes of the general theory rather than isolated instances, plus exact constants for four classes - out-trees 0, two-layer hubs 1, outerplanar two-exit interval spines 1 (sharp), series-parallel at most 1. Improved but not settled: the planar lower bound rises to $1.17353531974518$ against the known ceiling 2, and every exact-two-path instance whose rows touch at most three terminals satisfies $C\le2$, the first unconditional constant for an unbounded class. The universal question is untouched - it reduces here to a single factor-two merger statement with certified wall $K^*\ge2.5652\ldots$, twice the refined general lower bound $1.28260069\ldots$.

Recorded attempts

Evidence graph

Connected research record