====== Tim Chow ======

====== The Ring Grooming Problem: Combinatorial Optimization in Modern Telecommunications Networks ======

===== Abstract for the Combinatorics and Number Theory Seminar 2001 December 5 =====

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.