| Article ID: | iaor20052753 |
| Country: | France |
| Volume: | 37 |
| Issue: | 4 |
| Start Page Number: | 235 |
| End Page Number: | 247 |
| Publication Date: | Oct 2003 |
| Journal: | RAIRO Operations Research |
| Authors: | Crama Yves, Finke Gerd, Brauner Nadia, Wynants Christelle, Lemaire Pierre |
| Keywords: | heuristics |
In this paper, a graph partitioning problem that arises in the design of SONET/SDH networks is defined and formalized. Approximation algorithms with performance guarantees are presented. To solve this problem efficiently in practice, fast greedy algorithms and a tabu-search method are proposed and analyzed by means of an experimental study.