Polynomial-time approximation schemes for the Euclidean survivable network design problem
Författare
Summary, in English
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).
Avdelning/ar
- Computer Science
Publiceringsår
2002
Språk
Engelska
Sidor
973-984
Publikation/Tidskrift/Serie
Automata, Languages and Programming / Lecture Notes in Computer Science
Volym
2380
Dokumenttyp
Konferensbidrag
Förlag
Springer
Ämne
- Computer Science
Conference name
29th International Colloquium, ICALP 2002
Conference date
2002-07-08 - 2002-07-13
Conference place
Malaga, Spain
Status
Published
ISBN/ISSN/Övrigt
- ISSN: 1611-3349
- ISSN: 0302-9743