Problems / combinatorics
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$).