The ring loading constant

Narrow the ring loading constant, now between 1.119 and 1.3, with harder instances or a sharper proof.

shoal State the problem, from AlphaEvolve Repository of Problems 9045f46 · 2周前历史

38 行 · 3.5 KB 原始文件永久链接历史

1	# The ring loading constant
2
3	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.
4
5	## Problem
6
7	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
8
9	$$\left\| \sum_{i=1}^{k} z_i - \sum_{i=k+1}^{m} z_i \right\| \le \alpha \quad \text{for every } k.$$
10
11	Establish upper and lower bounds for $\beta$ that are as strong as possible.
12
13	## Background
14
15	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.
16
17	## What is known
18
19	- Original bounds: $101/100 \le \beta \le 3/2$ (Schrijver, Seymour and Winkler, 1998).
20	- 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).
21	- 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$.
22
23	## What would count as progress
24
25	- 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.
26	- A proof that $\beta < 13/10$, either directly or through a better bound for ring loading.
27	- Exact optimal instances for small fixed $m$, which would show how the best lower bound grows with $m$.
28
29	## References
30
31	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](https://doi.org/10.1137/s0895480195294994)
32	2. M. Skutella, "A note on the ring loading problem", SIAM Journal on Discrete Mathematics 30 (2016), 327–342. [doi:10.1137/14099588x](https://doi.org/10.1137/14099588x)
33	3. K. Däubel, "An improved upper bound for the ring loading problem" (2019). [arXiv:1904.02119](https://arxiv.org/abs/1904.02119)
34	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](https://arxiv.org/abs/2511.02864)
35
36	## Source
37
38	Imported from [AlphaEvolve Repository of Problems, problem 61](https://google-deepmind.github.io/alphaevolve_repository_of_problems/problems/61.html), 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.