**Problem of the Week**

**Math Club**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

seminars:comb:abstract.200112chow

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.

seminars/comb/abstract.200112chow.txt · Last modified: 2020/01/29 14:03 (external edit)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported