A note on the ring loading problem

DOI10.1137/14099588XMaRDI QIDQ2790401zbMATH OpenFDO

Authors Martin Skutella

Publication date 4 March 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.0789

zbMATH Keywords

load balancingunsplittable flowSONET ring

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Integer programming (90C10) Flows in graphs (05C21)

Abstract: 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.

Recommendations

• A note on the ring loading problem
• An improved upper bound for the ring loading problem
• The Ring Loading Problem
• On the ring loading problem with demand splitting.
• The Ring Loading Problem

Cites work

• Algorithms for routing around a rectangle
• Approximating the single source unsplittable min-cost flow problem
• Convex Combinations of Single Source Unsplittable Flows
• Edge-disjoint paths in planar graphs
• Multicommodity flows in planar graphs
• On the single-source unsplittable flow problem
• Optimal Load Balancing on Sonet Bidirectional Rings
• Single-Sink Multicommodity Flow with Side Constraints
• The Ring Loading Problem
• The Ring Loading Problem
• The analysis of evolutionary algorithms -- A proof that crossover really can help

Cited in

(8)

• A compact formulation of the ring loading problem with integer demand splitting
• Small additive error for unsplittable multicommodity flow in outerplanar graphs
• A note on the ring loading problem
• Optimal online ring routing
• Online mixed ring covering problem with two nodes
• Unsplittable multicommodity flows in outerplanar graphs
• The weighted link ring loading problem
• An improved upper bound for the ring loading problem

This page was built for publication: A note on the ring loading problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2790401)