2014/05/05 by Martin Skutella, Skutella, Martin · 1 citation
Engineering · #05C21 #90C27 #Advanced Optical Network Technologies #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #Vehicle Routing Optimization Methods #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1405.0789
openalex publication_date 2014/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Ring Loading Problem is an optimal routing problem arising in the planning of optical communication networks which use bidirectional SONET rings. In mathematical terms, it is an unsplittable multicommodity flow problem on undirected ring networks. We prove that any split routing solution to the Ring Loading Problem can be turned into an unsplittable solution while increasing the load on any edge of the ring by no more than +(19/14)D, where D is the maximum demand value. This improves upon a classical result of Schrijver, Seymour, and Winkler (1998) who obtained a slightly larger bound of +(3/2)D. We also present an improved lower bound of +1.1 D (previously +1.01 D) on the best possible bound and disprove a famous long-standing conjecture of Schrijver et al. in this context.