Fast approximation schemes for Euclidean multiconnectivity problems
(2000) 27th international colloquium / ICALP 2000 In Automata, languages and programming / Lecture notes in computer science 1853. p.856868 Abstract
 We present new polynomialtime approximation schemes (PTAS) for
several basic minimumcost multiconnectivity problems in geometrical graphs.
We focus on low connectivity requirements. Each of our schemes either signifi
cantly improves the previously known upper timebound 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 multidimensional 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 polynomialtime approximation schemes (PTAS) for
several basic minimumcost multiconnectivity problems in geometrical graphs.
We focus on low connectivity requirements. Each of our schemes either signifi
cantly improves the previously known upper timebound 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 multidimensional 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 polynomialtime 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 submultigraphs having good decomposition
and approximation properties and a simple subgraph connectivity
characterization. By using merely the spanner transformations, we obtain a very
fast polynomialtime approximation scheme for finding a minimumcost kedge
connected multigraph spanning a set of points in a multidimensional Euclidean
space. For any constant dimension, ", and k, this PTAS runs in time O(n log n).
Furthermore, by showing a lowcost transformation of a kedge connected graph
maintaining the kedge connectivity and developing novel decomposition properties,
we derive a PTAS for Euclidean minimumcost kedge connectivity. It is
substantially faster than that previously known.
Finally, by extending our techniques, we obtain the first PTAS for the problem
of Euclidean minimumcost Steiner biconnectivity. This scheme runs in time
O(n log n) for any constant dimension and ". As a byproduct, we get the first
known nontrivial upper bound on the number of Steiner points in an optimal
solution to an instance of Euclidean minimumcost Steiner biconnectivity. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/526600
 author
 Czumaj, Artur and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2000
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 fast approximation schemes, Euclidean multiconnectivity 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
 e5bb9c19175e4a9dae6537fdc069cda9 (old id 526600)
 date added to LUP
 20070913 14:13:15
 date last changed
 20180909 04:35:56
@inproceedings{e5bb9c19175e4a9dae6537fdc069cda9, abstract = {We present new polynomialtime approximation schemes (PTAS) for<br/><br> several basic minimumcost multiconnectivity 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 timebound 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 multidimensional 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 polynomialtime 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 submultigraphs 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 polynomialtime approximation scheme for finding a minimumcost kedge<br/><br> connected multigraph spanning a set of points in a multidimensional 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 lowcost transformation of a kedge connected graph<br/><br> maintaining the kedge connectivity and developing novel decomposition properties,<br/><br> we derive a PTAS for Euclidean minimumcost kedge 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 minimumcost 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 nontrivial upper bound on the number of Steiner points in an optimal<br/><br> solution to an instance of Euclidean minimumcost Steiner biconnectivity.}, author = {Czumaj, Artur and Lingas, Andrzej}, booktitle = {Automata, languages and programming / Lecture notes in computer science}, isbn = {3540677151}, keyword = {fast approximation schemes,Euclidean multiconnectivity problems,geometrical graphs}, language = {eng}, pages = {856868}, publisher = {Springer}, title = {Fast approximation schemes for Euclidean multiconnectivity problems}, volume = {1853}, year = {2000}, }