The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

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

På svenska

Author

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

Department/s

  • Computer Science

Publishing year

2002

Language

English

Pages

973-984

Publication/Series

Automata, Languages and Programming / Lecture Notes in Computer Science

Volume

2380

Document type

Conference paper

Publisher

Springer

Topic

  • 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/Other

  • ISSN: 1611-3349
  • ISSN: 0302-9743