The ring loading problem

Alexander Schrijver, Paul Seymour, Peter Winkler

Research output: Contribution to journalArticlepeer-review

102 Scopus citations

Abstract

The following problem arose in the planning of optical communications networks which use bidirectional SONET rings. Traffic demands di,j are given for each pair of nodes in an n-node ring; each demand must be routed one of the two possible ways around the ring. The object is to minimize the maximum load on the cycle, where the load of an edge is the sum of the demands routed through that edge. We provide a fast, simple algorithm which achieves a load that is guaranteed to exceed the optimum by at most 3/2 times the maximum demand, and that performs even better in practice. En route we prove the following curious lemma: for any X1,...,Xn ∈[0,1] there exist y1,...,yn such that for each k, [yk] = xk and equation presented.

Original languageEnglish (US)
Pages (from-to)1-14
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume11
Issue number1
DOIs
StatePublished - Feb 1998

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Load balancing
  • Optical network design
  • SONET ring

Fingerprint Dive into the research topics of 'The ring loading problem'. Together they form a unique fingerprint.

Cite this