The ring loading constant

Routing demands around a ring network without splitting them costs at most a bounded extra load compared with split routing. The sharp extra factor is a combinatorial constant known only to lie between 1.119 and 1.3; lower bounds are explicit instances that can be checked by brute force over all $2^m$ sign choices.

Problem

Let $\beta$ be the infimum of all reals $\alpha$ with the following property: for every $m \ge 1$ and all non-negative reals $u_1, \dots, u_m$ and $v_1, \dots, v_m$ with $u_i + v_i \le 1$, there are $z_1, \dots, z_m$ with $z_k \in \{v_k, -u_k\}$ for each $k$ and

$$\left| \sum_{i=1}^{k} z_i - \sum_{i=k+1}^{m} z_i \right| \le \alpha \quad \text{for every } k.$$

Establish upper and lower bounds for $\beta$ that are as strong as possible.

Background

The Ring Loading Problem arose in the 1990s from the design of SONET rings in telecommunication networks: route each demand between two nodes of a cycle clockwise or counter-clockwise so that the maximum load on an edge is as small as possible. If $L$ is the best unsplittable load, $L^*$ the best load when demands may be split, and $D$ the largest demand, Schrijver, Seymour and Winkler (1998) proved $L \le L^* + \tfrac32 D$ and extracted from their work the combinatorial statement above; improved ring loading bounds have since given improved bounds on $\beta$. They conjectured that $L \le L^* + D$ always holds, which Skutella disproved.

What is known

• Original bounds: $101/100 \le \beta \le 3/2$ (Schrijver, Seymour and Winkler, 1998).
• Improvements: $11/10 \le \beta \le 19/14$ (Skutella, 2016), the lower bound coming from an explicit instance that refutes the conjecture; $\beta \le 13/10$ (Däubel, 2019).
• Current lower bound: $\beta \ge 1.119$ (Georgiev, Gómez-Serrano, Tao and Wagner, 2025), from an instance with $m = 15$ found by computer search; recomputing all $2^{15}$ sign choices for that instance gives a value of $1.1190475\ldots$.

What would count as progress

• An instance $(u_i, v_i)_{i \le m}$ whose best sign choice has value above $1.1190$. It is verified exactly by trying all $2^m$ choices of $z$, which takes seconds to minutes for $m$ up to about 25, and the data should be given in rational form so that the check needs no floating point.
• A proof that $\beta < 13/10$, either directly or through a better bound for ring loading.
• Exact optimal instances for small fixed $m$, which would show how the best lower bound grows with $m$.

References

1. A. Schrijver, P. Seymour and P. Winkler, "The ring loading problem", SIAM Journal on Discrete Mathematics 11 (1998), 1–14. doi:10.1137/s0895480195294994
2. M. Skutella, "A note on the ring loading problem", SIAM Journal on Discrete Mathematics 30 (2016), 327–342. doi:10.1137/14099588x
3. K. Däubel, "An improved upper bound for the ring loading problem" (2019). arXiv:1904.02119
4. B. Georgiev, J. Gómez-Serrano, T. Tao and A. Z. Wagner, "Mathematical exploration and discovery at scale" (2025), Problem 6.61. arXiv:2511.02864

Source

Imported from AlphaEvolve Repository of Problems, problem 61, curated by Google DeepMind. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.