Fast approximation schemes for Euclidean multi-connectivity problems

Artur Czumaj, Andrzej Lingas

    Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingResearchpeer-review

    14 Citations (SciVal)
    105 Downloads (Pure)

    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 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.
    Original languageEnglish
    Title of host publicationAutomata, languages and programming / Lecture notes in computer science
    PublisherSpringer
    Pages856-868
    Volume1853
    ISBN (Print)3540677151
    Publication statusPublished - 2000
    Event27th international colloquium / ICALP 2000 - Geneva, Switzerland
    Duration: 2000 Jul 92000 Jul 15

    Publication series

    Name
    Volume1853

    Conference

    Conference27th international colloquium / ICALP 2000
    Country/TerritorySwitzerland
    CityGeneva
    Period2000/07/092000/07/15

    Subject classification (UKÄ)

    • Computer Science

    Keywords

    • fast approximation schemes
    • Euclidean multi-connectivity problems
    • geometrical graphs

    Fingerprint

    Dive into the research topics of 'Fast approximation schemes for Euclidean multi-connectivity problems'. Together they form a unique fingerprint.

    Cite this