Many modern telecommunications networks are based on so-called ``bidirectional SONET rings, whose interconnection graph is a cycle. One might suppose that optimal routing on a cycle graph would be a trivial problem, but this is not always true because certain variables are constrained to assume integer values. Schrijver, Seymour, Winkler, and others have studied the so-called ``ring loading problem, in which the cost of a network is assumed to be proportional to the amount of traffic on the edge with the heaviest load, and they have obtained good approximation algorithms.

Often, however, a more realistic assumption is that the cost of a network is proportional to the amount of electronic hardware needed to support the traffic. This assumption leads to the ``ring grooming problem,'' which appears to be harder than the ring loading problem. Our main result is a constant-factor approximation algorithm (i.e., a polynomial-time algorithm that produces a solution whose cost is within a constant multiplicative factor of the optimum) for uniform traffic. The algorithm is based on the construction of covering designs. The problem of finding a constant-factor approximation algorithm for an arbitrary set of traffic demands remains open.

No background in telecommunications will be assumed.

This is joint work with Philip Lin.