Powered by OpenAIRE graph
Found an issue? Give us feedback
ZENODOarrow_drop_down
ZENODO
Preprint . 2026
License: CC BY
Data sources: Datacite
ZENODO
Preprint . 2026
License: CC BY
Data sources: Datacite
addClaim

Deletion-Star Ceilings and a 1.28249 Lower Bound for Cost-Preserving Single-Source Unsplittable Flows

Authors: Nikolenko, Sergey;

Deletion-Star Ceilings and a 1.28249 Lower Bound for Cost-Preserving Single-Source Unsplittable Flows

Abstract

For a single-source unsplittable flow we ask for a rounding of a feasible fractional flow $\textbf{x}$ to one path per terminal that satisfies both the cost constraint $\textbf{c}^\top\textbf{y}\le\textbf{c}^\top\textbf{x}$ and the overload constraint $y_a\le x_a+Cd_{\max}$ on every arc. Goemans conjectured $C=1$; this was disproved in July 2026 by a seven-vertex instance with critical constant $16/15$, and our previous work raised the bound to $(299-41\sqrt{41})/32=1.1397\ldots$ with a four-terminal planar family. We continue that program on three fronts. Records: we present a seventeen-terminal common-point interval instance that certifies $$ C\ \ge\ \frac{1282494797984843521}{10^{18}}=1.282494797984843521\ldots, $$ verified independently by enumerating all $2^{17}$ routings from the raw $67$-arc list, together with an $18$-atom exact convex-hull certificate. Upper bounds: we prove the first unconditional upper bound below 2 for a nontrivial family of the extremal cells. Representing the class as a weighted two-permutation prefix system, we introduce the deletion-star residual $B$, show that a bound $B\le\beta$ yields congestion at most $1+\beta$, and prove that on the codimension two cost face defined by the equality $\sum_if_i=k-2$ one always has $B\le\tfrac12$, for arbitrary orders, arbitrary demands (zero demands allowed) and arbitrary shares. This gives congestion at most $\tfrac32$ on every common-point cell whose first cost-good routing rank is $k-1$. The constant $\tfrac12$ is asymptotically sharp at every fixed codimension $q$, with the exact value $B_{mq,q}=\tfrac12-\tfrac1{2m}$, and the sharpness persists through a non-divisible two-scale demand perturbation. Throughout the paper, theorems are named by the mechanism that proves them (proportional credits, a single deletion star, the multi-star threshold), and subsequent negative results (of which this program has produced several) make the scope of these methods more narrow rather than retract theorems. Structure: we show that the naive continuum limit of the class has value zero, so the class supremum is a genuinely microscopic quantity; we give a cost-preserving transfer through Knuth's two-way rounding network with exact radius $B(\textbf{d})=\min_{\lambda\ge0}(\lambda+\sum_i|d_i-\lambda|)$; we prove the lower-box statement (LB) for all $2^{k-1}$ deque orders and for a maximal switched-interval class of signed tree networks; and we record exact minimal obstructions showing that every scalar two-order induction fails, leaving a convex Pareto transfer as the surviving mechanism. Finally, literal three-order overlays are dominated at $6/5$. Every numerical claim is certified in exact rational or symbolic arithmetic by programs that rebuild each instance from its raw arc list; the artifacts are published at https://github.com/snikolenko/unsplittable-flows.

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!