The University of Michigan Combinatorics Seminar


Abstract 

Many modern telecommunications networks are based on socalled
"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 socalled "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.
