The Ring Grooming Problem:
combinatorial optimization in modern
Timothy Y. Chow
Tellabs Research Center
refreshments at 3:45pm
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
No background in telecommunications will be assumed. This is joint work
with Philip Lin.
Speaker's Contact Info: tchow(at-sign)alum.mit.edu
Return to seminar home page
Page loaded on September 10, 2001 at 09:39 PM.
Copyright © 1998-99, Sara C. Billey.
All rights reserved.