The ring loading problem

The following problem arose in the planning of optical communications netwo rks which use bidirectional. SONET rings. Traffic demands d(i,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 maxim um load on the cycle, where the load of an edge is the sum of the demands r outed through that edge. We provide a fast, simple algorithm which achieves a load that is guarantee d to exceed the optimum by at most 3/2 times the maximum demand, and that p erforms even better in practice. En route we prove the following curious le mma: for any x(1),...,x(n) is an element of [0, 1] there exist y(1),..., y( n) such that for each k, \y(k)\ = x(k) and [GRAPHICS] [This article is reprinted here (with updates) from SIAM J. Discrete Math., 11 (1998), pp. 1-14. New developments include a 1+epsilon approximation al gorithm and a variation of ring loading in the setting of wavelength divisi on multiplexing; remarks added for this printing, about these and other iss ues, are enclosed in brackets.]