Polynomialtime approximation schemes for the Euclidean survivable network design problem
(2002) 29th International Colloquium, ICALP 2002 In Automata, Languages and Programming / Lecture Notes in Computer Science 2380. p.973984 Abstract
 The survivable network design problem is a classical problem in combinatorial optimization of constructing a minimumcost 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 polynomialtime 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 minimumcost 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 polynomialtime 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 polynomialtime approximation schemes work for both vertex and edgeconnectivity 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 edgeconnectivity 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:
http://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
 in
 Automata, Languages and Programming / Lecture Notes in Computer Science
 volume
 2380
 pages
 973  984
 publisher
 Springer
 conference name
 29th International Colloquium, ICALP 2002
 external identifiers

 wos:000180069500083
 scopus:84869152022
 ISSN
 16113349
 03029743
 DOI
 10.1007/3540454659_83
 language
 English
 LU publication?
 yes
 id
 b7544d27899d4b43959525fc030132ed (old id 321134)
 date added to LUP
 20070815 13:58:08
 date last changed
 20170305 03:40:27
@inproceedings{b7544d27899d4b43959525fc030132ed, abstract = {The survivable network design problem is a classical problem in combinatorial optimization of constructing a minimumcost 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 polynomialtime 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 polynomialtime approximation schemes work for both vertex and edgeconnectivity 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 edgeconnectivity 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 = {16113349}, language = {eng}, pages = {973984}, publisher = {Springer}, title = {Polynomialtime approximation schemes for the Euclidean survivable network design problem}, url = {http://dx.doi.org/10.1007/3540454659_83}, volume = {2380}, year = {2002}, }