Premium
The ring grooming problem
Author(s) -
Chow Timothy Y.,
Lin Philip J.
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20029
Subject(s) - traffic grooming , synchronous optical networking , ring (chemistry) , constant (computer programming) , mathematics , time complexity , upper and lower bounds , linear programming , linear programming relaxation , mathematical optimization , combinatorics , computer science , discrete mathematics , computer network , wavelength division multiplexing , mathematical analysis , wavelength , chemistry , physics , optoelectronics , organic chemistry , programming language
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. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 194–202 2004