### Sidebar

seminars:comb:abstract.200112chow

# 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.