# Approximation algorithms for the design of SDH/SONET networks

Nadia Brauner; Yves Crama; Gerd Finke; Pierre Lemaire; Christelle Wynants

RAIRO - Operations Research (2010)

- Volume: 37, Issue: 4, page 235-247
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBrauner, Nadia, et al. "Approximation algorithms for the design of SDH/SONET networks." RAIRO - Operations Research 37.4 (2010): 235-247. <http://eudml.org/doc/105293>.

@article{Brauner2010,

abstract = {
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.
},

author = {Brauner, Nadia, Crama, Yves, Finke, Gerd, Lemaire, Pierre, Wynants, Christelle},

journal = {RAIRO - Operations Research},

keywords = {Graph partitioning; approximations; heuristics; tabu; SONET/SDH networks.; graph partitioning; SONET/SDH networks},

language = {eng},

month = {3},

number = {4},

pages = {235-247},

publisher = {EDP Sciences},

title = {Approximation algorithms for the design of SDH/SONET networks},

url = {http://eudml.org/doc/105293},

volume = {37},

year = {2010},

}

TY - JOUR

AU - Brauner, Nadia

AU - Crama, Yves

AU - Finke, Gerd

AU - Lemaire, Pierre

AU - Wynants, Christelle

TI - Approximation algorithms for the design of SDH/SONET networks

JO - RAIRO - Operations Research

DA - 2010/3//

PB - EDP Sciences

VL - 37

IS - 4

SP - 235

EP - 247

AB -
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.

LA - eng

KW - Graph partitioning; approximations; heuristics; tabu; SONET/SDH networks.; graph partitioning; SONET/SDH networks

UR - http://eudml.org/doc/105293

ER -

## References

top- R. Aringhieri and M. Dell'Amico, A Variable-Neighborhood Variable-Objective Tabu Search Algorithm for the SONET Ring Assignment with Capacity Constraints. DISMI, Università di Modena e Reggio Emilia, 10 (2001).
- N. Brauner, Y. Crama, P. Lemaire and C. Wynants, Complexité et approximation pour la conception de réseaux SONET/SDH. Technical Report 61, Les Cahiers du Laboratoire Leibniz-IMAG, (October 2002). URIhttp://www-leibniz.imag.fr/LesCahiers/
- N. Brauner and P. Lemaire, A Set-Covering Approach for SONET Network Design. Technical Report 62, Les Cahiers du Laboratoire Leibniz-IMAG (October 2002). URIhttp://www-leibniz.imag.fr/LesCahiers/
- V. Chvátal, A Greedy Heuristic for the Set-Covering Problem. Math. Oper. Res.4 (1979) 233-235 . Zbl0443.90066
- ETSI. ETSI - Telecom Standards. URIhttp://www.etsi.org
- ETSI. Transmission and Multiplexing (TM); Synchronous Digital Hierarchy (SDH); Network protection schemes; Rings and other schemes. Technical specification (November 1997). ref: TS 101 010 v1.1.1.
- ETSI. Transmission and Multiplexing (TM); Synchronous Digital Hierarchy (SDH); Network protection schemes; Types and characteristics. Technical specification (November 1997). ref: TS 101 009 v1.1.1.
- B. Fortz, P. Soriano and C. Wynants, A Tabu Search Algorithm for Self-Healing Ring Network Design. Eur. J. Oper. Res.151 (2003). Zbl1053.90020
- M.R. Garey and D.S. Johnson, Computers and Intractability (A Guide to the Theory of NP-Completeness). W.H. Freeman And Company (1979). Zbl0411.68039
- F. Glover and M. Laguna, Modern Heuristic Techniques for Combinatorial Problems, Chapter 3: Tabu Search. C.R. Reeves, Blackwell Scientific Publications edition (1993).
- F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, London (1997).
- O. Goldschmidt, D.S. Hochbaum, A. Levin and E.V. Olinick, The SONET Edge-Partition Problem. Networks41 (2003) 13-23 . Zbl1026.90076
- O. Goldschmidt, A. Laugier and E.V. Olinick, SONET/SDH Ring Assignment with Capacity Constraints. Discrete Appl. Math.129 (2003) 99-128 . Zbl1023.68003
- I. Holyer, The NP-completeness of some edge-partition problems. SIAM J. Comput.4 (1981) 713-717. Zbl0468.68069
- D.S. Johnson, A. Demers, J.D. Ullman, M.R. Garey and R.L. Graham, Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput.3 (1974) 299-325 . Zbl0297.68028
- S. Khanna, A Polynomial Time Approximation Scheme for the SONET Ring Loading Problem. Bell Labs Technical Journal (1997) 36-41.
- M. Laguna, Clustering for the Design of SONET Rings in Interoffice Telecommunications. Manage. Sci.40 (1994) 1533-1541. Zbl0823.90040
- Y. Lee, H.D. Sherali, J. Han and S. Kim, A branch-and-cut algorithm for solving an intraring synchronous optical network design problem. Networks35 (2000) 223-232 . Zbl0985.90093
- P. Lemaire, Optimisation de réseaux SONET/SDH : éléments théoriques et résolution pratique (juin 2001). Mémoire de DEA.
- S. Masuyama and T. Ibaraki, Chain Packing in Graphs. Algorithmica6 (1991) 826-839 . Zbl0731.68088
- D. Mili, Self-Healing Ring Architectures for SONET Network Applications. URIhttp://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol2/dm9/article2.html
- A. Schrijver, P. Seymour and P. Winkler, The Ring Loading Problem. SIAM J. Discrete Math.11 (1998) 1-14 . Zbl0910.90135
- A. Sutter, F. Vanderbeck and L.A. Wolsey, Optimal Placement of Add/Drop Multiplexers: Heuristic and Exact Algorithms. Oper. Res.46 (1998) 719-728. Zbl0987.90014
- T.-H. Wu, Fiber Network Service Survivability. Artech House, Inc. (1992).
- The SONET Home Page. URIhttp://www.sonet.com

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.