Advanced

Polynomial-time approximation schemes for the Euclidean survivable network design problem

Czumaj, A; Lingas, Andrzej LU and Zhao, HR (2002) 29th International Colloquium, ICALP 2002 In Automata, Languages and Programming / Lecture Notes in Computer Science 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:
author
organization
publishing date
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
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
2007-08-15 13:58:08
date last changed
2017-03-05 03:40:27
@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},
  volume       = {2380},
  year         = {2002},
}