The Ring Grooming Problem: Combinatorial
Optimization in Modern Telecommunications Networks

Many modern telecommunications networks are based on so-called "bidirectional SONET rings." 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.