Polynomial-time approximation schemes for the Euclidean survivable network design problem
(2002) 29th International Colloquium, ICALP 2002 2380. p.973-984- Abstract
- The survivable network design problem is a classical problem in combinatorial optimization of constructing a minimum-cost subgraph satisfying predetermined connectivity requirements. In this paper we consider its geometric version in which the input is a complete Euclidean graph. We assume that each vertex v has been assigned a connectivity requirement r(upsilon).. The output subgraph is supposed to have the vertex- (or edge-, respectively) connectivity of at least min{r(upsilon), r(u)} for any pair of vertices upsilon, u. We present the first polynomial-time approximation schemes (PTAS) for basic variants of the survivable network design problem in Euclidean graphs. We first show a PTAS for the Steiner tree problem, which is the... (More)
- The survivable network design problem is a classical problem in combinatorial optimization of constructing a minimum-cost subgraph satisfying predetermined connectivity requirements. In this paper we consider its geometric version in which the input is a complete Euclidean graph. We assume that each vertex v has been assigned a connectivity requirement r(upsilon).. The output subgraph is supposed to have the vertex- (or edge-, respectively) connectivity of at least min{r(upsilon), r(u)} for any pair of vertices upsilon, u. We present the first polynomial-time approximation schemes (PTAS) for basic variants of the survivable network design problem in Euclidean graphs. We first show a PTAS for the Steiner tree problem, which is the survivable network design problem with r(upsilon) is an element of {0, 1} for any vertex upsilon. Then, we extend it to include the most widely applied case where r(upsilon) is an element of {0, 1, 2} for any vertex upsilon. Our polynomial-time approximation schemes work for both vertex- and edge-connectivity requirements in time 0 (n log n), where the constants depend on the dimension and the accuracy of approximation. Finally, we observe that our techniques yield also a PTAS for the multigraph variant of the problem where the edge-connectivity requirements satisfy r(upsilon) is an element of {0, 1,..., k} and k = O(1). (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/321134
- author
- Czumaj, A ; Lingas, Andrzej LU and Zhao, HR
- organization
- publishing date
- 2002
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Automata, Languages and Programming / Lecture Notes in Computer Science
- volume
- 2380
- pages
- 973 - 984
- publisher
- Springer
- conference name
- 29th International Colloquium, ICALP 2002
- conference location
- Malaga, Spain
- conference dates
- 2002-07-08 - 2002-07-13
- external identifiers
-
- wos:000180069500083
- scopus:84869152022
- ISSN
- 1611-3349
- 0302-9743
- DOI
- 10.1007/3-540-45465-9_83
- language
- English
- LU publication?
- yes
- id
- b7544d27-899d-4b43-9595-25fc030132ed (old id 321134)
- date added to LUP
- 2016-04-01 12:36:08
- date last changed
- 2024-01-09 02:07:40
@inproceedings{b7544d27-899d-4b43-9595-25fc030132ed,
abstract = {{The survivable network design problem is a classical problem in combinatorial optimization of constructing a minimum-cost subgraph satisfying predetermined connectivity requirements. In this paper we consider its geometric version in which the input is a complete Euclidean graph. We assume that each vertex v has been assigned a connectivity requirement r(upsilon).. The output subgraph is supposed to have the vertex- (or edge-, respectively) connectivity of at least min{r(upsilon), r(u)} for any pair of vertices upsilon, u. We present the first polynomial-time approximation schemes (PTAS) for basic variants of the survivable network design problem in Euclidean graphs. We first show a PTAS for the Steiner tree problem, which is the survivable network design problem with r(upsilon) is an element of {0, 1} for any vertex upsilon. Then, we extend it to include the most widely applied case where r(upsilon) is an element of {0, 1, 2} for any vertex upsilon. Our polynomial-time approximation schemes work for both vertex- and edge-connectivity requirements in time 0 (n log n), where the constants depend on the dimension and the accuracy of approximation. Finally, we observe that our techniques yield also a PTAS for the multigraph variant of the problem where the edge-connectivity requirements satisfy r(upsilon) is an element of {0, 1,..., k} and k = O(1).}},
author = {{Czumaj, A and Lingas, Andrzej and Zhao, HR}},
booktitle = {{Automata, Languages and Programming / Lecture Notes in Computer Science}},
issn = {{1611-3349}},
language = {{eng}},
pages = {{973--984}},
publisher = {{Springer}},
title = {{Polynomial-time approximation schemes for the Euclidean survivable network design problem}},
url = {{http://dx.doi.org/10.1007/3-540-45465-9_83}},
doi = {{10.1007/3-540-45465-9_83}},
volume = {{2380}},
year = {{2002}},
}