Problems / algorithms-optimization
algorithms-optimization / Combinatorial optimization; unsplittable flow
Exact SSUF scenario-count ladder on the four-terminal planar gadget
For the released four-terminal planar acyclic single-source unsplittable-flow gadget, require one unsplittable routing to be no more expensive than a prescribed fractional routing under each of $m$ strictly positive full-demand route-cost-difference scenarios. What is the worst-case normalized additive upper-arc deviation? The v0.3.0 fixed-gadget scenario-count ladder proves
$$\beta_G^{(m,+)}=
\begin{cases}
\dfrac{299-41\sqrt{41}}{32},&m=1,\\
\dfrac{17}{8},&m=2,\\
3,&m=3,\\
4,&m\ge4.
\end{cases}$$
The $m\ge2$ values are non-attained suprema; no attainment or non-attainment assertion is made for $m=1$. The one-scenario value also holds for legally realizable signed and zero route-cost differences; no such multi-scenario extension is claimed.