The ring grooming problem

Details The ring grooming problem The ring grooming problem

2001-01-10

arxiv.org/abs/math/0101091v3

Mathematics

Optimization and Control

Results extended from uniform traffic to quasi-uniform traffic

Scientific paper

The problem of minimizing the number of bidirectional SONET rings required to support a given traffic demand has been studied by several researchers. Here we study the related ``ring grooming problem'' of minimizing the number of add/drop locations instead of the number of rings; in a number of situations this is a better approximation to the true equipment cost. Our main result is a new lower bound for the case of uniform traffic. This allows us to prove that a certain simple algorithm for uniform traffic is in fact a constant-factor approximation algorithm, and it also demonstrates that known lower bounds for the general problem--in particular, the linear programming relaxation--are not within a constant factor of the optimum. We also show that our results for uniform traffic extend readily to the more practically important case of quasi-uniform traffic. Finally, we show that if the number of nodes on the ring is fixed, then ring grooming is solvable in polynomial time; however, whether ring grooming is fixed-parameter tractable is still an open question.

Affiliated with

Also associated with

No associations

Rating

The ring grooming problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The ring grooming problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The ring grooming problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-66196