A NOTE ON THE RING LOADING PROBLEM

作者：Skutella Martin^*

来源：SIAM Journal on Discrete Mathematics, 2016, 30(1): 327-342.

DOI：10.1137/14099588X

• unsplittable flow
• SONET ring
• load balancing

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/14D, 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/2D. We also present an improved lower bound of 11/10D (previously 101/100D) on the best possible bound and disprove a famous long-standing conjecture of Schrijver, Seymour, and Winker in this context.

• 出版日期2016