Fast approximation schemes for Euclidean multi-connectivity problems
Author
Summary, in English
We present new polynomial-time approximation schemes (PTAS) for
several basic minimum-cost multi-connectivity problems in geometrical graphs.
We focus on low connectivity requirements. Each of our schemes either signifi-
cantly improves the previously known upper time-bound or is the first PTAS for
the considered problem.
We provide a randomized approximation scheme for finding a biconnected graph
spanning a set of points in a multi-dimensional Euclidean space and having the
expected total cost within (1+") of the optimum. For any constant dimension and
", our scheme runs in time O(n log n). It can be turned into Las Vegas one without
affecting its asymptotic time complexity, and also efficiently derandomized.
The only previously known truly polynomial-time approximation (randomized)
scheme for this problem runs in expected time n (log n)O((log log n)9) in the
simplest planar case. The efficiency of our scheme relies on transformations of
nearly optimal low cost special spanners into sub-multigraphs having good decomposition
and approximation properties and a simple subgraph connectivity
characterization. By using merely the spanner transformations, we obtain a very
fast polynomial-time approximation scheme for finding a minimum-cost k-edge
connected multigraph spanning a set of points in a multi-dimensional Euclidean
space. For any constant dimension, ", and k, this PTAS runs in time O(n log n).
Furthermore, by showing a low-cost transformation of a k-edge connected graph
maintaining the k-edge connectivity and developing novel decomposition properties,
we derive a PTAS for Euclidean minimum-cost k-edge connectivity. It is
substantially faster than that previously known.
Finally, by extending our techniques, we obtain the first PTAS for the problem
of Euclidean minimum-cost Steiner biconnectivity. This scheme runs in time
O(n log n) for any constant dimension and ". As a byproduct, we get the first
known non-trivial upper bound on the number of Steiner points in an optimal
solution to an instance of Euclidean minimum-cost Steiner biconnectivity.
several basic minimum-cost multi-connectivity problems in geometrical graphs.
We focus on low connectivity requirements. Each of our schemes either signifi-
cantly improves the previously known upper time-bound or is the first PTAS for
the considered problem.
We provide a randomized approximation scheme for finding a biconnected graph
spanning a set of points in a multi-dimensional Euclidean space and having the
expected total cost within (1+") of the optimum. For any constant dimension and
", our scheme runs in time O(n log n). It can be turned into Las Vegas one without
affecting its asymptotic time complexity, and also efficiently derandomized.
The only previously known truly polynomial-time approximation (randomized)
scheme for this problem runs in expected time n (log n)O((log log n)9) in the
simplest planar case. The efficiency of our scheme relies on transformations of
nearly optimal low cost special spanners into sub-multigraphs having good decomposition
and approximation properties and a simple subgraph connectivity
characterization. By using merely the spanner transformations, we obtain a very
fast polynomial-time approximation scheme for finding a minimum-cost k-edge
connected multigraph spanning a set of points in a multi-dimensional Euclidean
space. For any constant dimension, ", and k, this PTAS runs in time O(n log n).
Furthermore, by showing a low-cost transformation of a k-edge connected graph
maintaining the k-edge connectivity and developing novel decomposition properties,
we derive a PTAS for Euclidean minimum-cost k-edge connectivity. It is
substantially faster than that previously known.
Finally, by extending our techniques, we obtain the first PTAS for the problem
of Euclidean minimum-cost Steiner biconnectivity. This scheme runs in time
O(n log n) for any constant dimension and ". As a byproduct, we get the first
known non-trivial upper bound on the number of Steiner points in an optimal
solution to an instance of Euclidean minimum-cost Steiner biconnectivity.
Department/s
- Computer Science
Publishing year
2000
Language
English
Pages
856-868
Publication/Series
Automata, languages and programming / Lecture notes in computer science
Volume
1853
Full text
- Available as PDF - 150 kB
- Download statistics
Document type
Conference paper
Publisher
Springer
Topic
- Computer Science
Keywords
- fast approximation schemes
- Euclidean multi-connectivity problems
- geometrical graphs
Conference name
27th international colloquium / ICALP 2000
Conference date
2000-07-09 - 2000-07-15
Conference place
Geneva, Switzerland
Status
Published
ISBN/ISSN/Other
- ISBN: 3540677151