Advanced

Fast approximation schemes for Euclidean multi-connectivity problems

Czumaj, Artur and Lingas, Andrzej LU (2000) 27th international colloquium / ICALP 2000 In Automata, languages and programming / Lecture notes in computer science 1853. p.856-868
Abstract
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... (More)
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. (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
keywords
fast approximation schemes, Euclidean multi-connectivity problems, geometrical graphs
in
Automata, languages and programming / Lecture notes in computer science
volume
1853
pages
856 - 868
publisher
Springer
conference name
27th international colloquium / ICALP 2000
external identifiers
  • Scopus:84974604023
ISBN
3540677151
language
English
LU publication?
yes
id
e5bb9c19-175e-4a9d-ae65-37fdc069cda9 (old id 526600)
date added to LUP
2007-09-13 14:13:15
date last changed
2016-10-13 04:46:24
@misc{e5bb9c19-175e-4a9d-ae65-37fdc069cda9,
  abstract     = {We present new polynomial-time approximation schemes (PTAS) for<br/><br>
several basic minimum-cost multi-connectivity problems in geometrical graphs.<br/><br>
We focus on low connectivity requirements. Each of our schemes either signifi-<br/><br>
cantly improves the previously known upper time-bound or is the first PTAS for<br/><br>
the considered problem.<br/><br>
We provide a randomized approximation scheme for finding a biconnected graph<br/><br>
spanning a set of points in a multi-dimensional Euclidean space and having the<br/><br>
expected total cost within (1+") of the optimum. For any constant dimension and<br/><br>
", our scheme runs in time O(n log n). It can be turned into Las Vegas one without<br/><br>
affecting its asymptotic time complexity, and also efficiently derandomized.<br/><br>
The only previously known truly polynomial-time approximation (randomized)<br/><br>
scheme for this problem runs in expected time n (log n)O((log log n)9) in the<br/><br>
simplest planar case. The efficiency of our scheme relies on transformations of<br/><br>
nearly optimal low cost special spanners into sub-multigraphs having good decomposition<br/><br>
and approximation properties and a simple subgraph connectivity<br/><br>
characterization. By using merely the spanner transformations, we obtain a very<br/><br>
fast polynomial-time approximation scheme for finding a minimum-cost k-edge<br/><br>
connected multigraph spanning a set of points in a multi-dimensional Euclidean<br/><br>
space. For any constant dimension, ", and k, this PTAS runs in time O(n log n).<br/><br>
Furthermore, by showing a low-cost transformation of a k-edge connected graph<br/><br>
maintaining the k-edge connectivity and developing novel decomposition properties,<br/><br>
we derive a PTAS for Euclidean minimum-cost k-edge connectivity. It is<br/><br>
substantially faster than that previously known.<br/><br>
Finally, by extending our techniques, we obtain the first PTAS for the problem<br/><br>
of Euclidean minimum-cost Steiner biconnectivity. This scheme runs in time<br/><br>
O(n log n) for any constant dimension and ". As a byproduct, we get the first<br/><br>
known non-trivial upper bound on the number of Steiner points in an optimal<br/><br>
solution to an instance of Euclidean minimum-cost Steiner biconnectivity.},
  author       = {Czumaj, Artur and Lingas, Andrzej},
  isbn         = {3540677151},
  keyword      = {fast approximation schemes,Euclidean multi-connectivity problems,geometrical graphs},
  language     = {eng},
  pages        = {856--868},
  publisher    = {ARRAY(0xbd2e118)},
  series       = {Automata, languages and programming / Lecture notes in computer science},
  title        = {Fast approximation schemes for Euclidean multi-connectivity problems},
  volume       = {1853},
  year         = {2000},
}