[en] 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.
Disciplines :
Engineering, computing & technology: Multidisciplinary, general & others
Author, co-author :
Brauner, Nadia
Crama, Yves ; Université de Liège - ULiège > HEC - École de gestion de l'ULiège > Recherche opérationnelle et gestion de la production
Aringhieri, R., Dell'Amico, M., (2001) A Variable-neighborhood Variable-objective Tabu Search Algorithm for the SONET Ring Assignment with Capacity Constraints, p. 10. , DISMI, Università di Modena e Reggio Emilia
Brauner, N., Crama, Y., Lemaire, P., Wynants, C., (2002) Complexité et Approximation pour la Conception de Réseaux SONET/SDH, , http://ww-leibniz.imag.fr/LesCahiers/, Technical Report 61, Les Cahiers du Laboratoire Leibniz-IMAG, October
Brauner, N., Lemaire, P., (2002) A Set-covering Approach for SONET Network Design, , http://www-leibniz.imag.fr/LesCahiers/, Technical Report 62, Les Cahiers du Laboratoire Leibniz-IMAG (October)
Chvátal, V., A Greedy Heuristic for the Set-Covering Problem (1979) Math. Oper. Res., 4, pp. 233-235
ETSI - Telecom Standards, , http://www.etsi.org
(1997) Network Protection Schemes
Rings and Other Schemes, , Transmission and Multiplexing (TM)
Fortz, B., Soriano, P., Wynants, C., A Tabu Search Algorithm for Self-Healing Ring Network Design (2003) Eur. J. Oper. Res., 151
Garey, M.R., Johnson, D.S., (1979) Computers and Intractability (A Guide to the Theory of NP-Completeness), , W.H. Freeman And Company
Glover, F., Laguna, M., (1993) Modern Heuristic Techniques for Combinatorial Problems, Chapter 3: Tabu Search, , C.R. Reeves, Blackwell Scientific Publications edition
Glover, F., Laguna, M., (1997) Tabu Search, , Kluwer Academic Publishers, London
Goldschmidt, O., Hochbaum, D.S., Levin, A., Olinick, E.V., The SONET Edge-Partition Problem (2003) Networks, 41, pp. 13-23
Goldschmidt, O., Laugier, A., Olinick, E.V., SONET/SDH Ring Assignment with Capacity Constraints (2003) Discrete Appl. Math., 129, pp. 99-128
Holyer, I., The NP-completeness of some edge-partition problems (1981) SIAM J. Comput., 4, pp. 713-717
Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L., Worst-case performance bounds for simple one-dimensional packing algorithms (1974) SIAM J. Comput., 3, pp. 299-325
Khanna, S., A Polynomial Time Approximation Scheme for the SONET Ring Loading Problem (1997) Bell Labs Technical Journal, pp. 36-41
Laguna, M., Clustering for the Design of SONET Rings in Interoffice Telecommunications (1994) Manage. Sci., 40, pp. 1533-1541
Lee, Y., Sherali, H.D., Han, J., Kim, S., A branch-and-cut algorithm for solving an intraring synchronous optical network design problem (2000) Networks, 35, pp. 223-232
Lemaire, P., (2001) Optimisation de Réseaux SONET/SDH: Éléments Théoriques et Résolution Pratique, , juin. Mémoire de DEA
Masuyama, S., Ibaraki, T., Chain Packing in Graphs (1991) Algorithmica, 6, pp. 826-839
Mili, D., Self-Healing Ring Architectures for SONET Network Applications, , http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vo12/dm9/article2.html
Schrijver, A., Seymour, P., Winkler, P., The Ring Loading Problem (1998) SIAM J. Discrete Math., 11, pp. 1-14
Sutter, A., Vanderbeck, F., Wolsey, L.A., Optimal Placement of Add/Drop Multiplexers: Heuristic and Exact Algorithms (1998) Oper. Res., 46, pp. 719-728
