O(1)-approximations for maximum movement problems

Piotr Berman, Erik D. Demaine, Morteza Zadimoghaddam

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    11 Scopus citations

    Abstract

    We develop constant-factor approximation algorithms for minimizing the maximum movement made by pebbles on a graph to reach a configuration in which the pebbles form a connected subgraph (connectivity), or interconnect a constant number of stationary nodes (Steiner tree). These problems model the minimization of the total time required to reconfigure a robot swarm to achieve a proximity (e.g., radio) network with these connectivity properties. Our approximation factors are tight up to constant factors, as none of these problems admit a (2 - ε)-approximation assuming P ≠ NP.

    Original languageEnglish (US)
    Title of host publicationApproximation, Randomization, and Combinatorial Optimization
    Subtitle of host publicationAlgorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings
    Pages62-74
    Number of pages13
    DOIs
    StatePublished - 2011
    Event14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011 - Princeton, NJ, United States
    Duration: Aug 17 2011Aug 19 2011

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume6845 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011
    Country/TerritoryUnited States
    CityPrinceton, NJ
    Period8/17/118/19/11

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'O(1)-approximations for maximum movement problems'. Together they form a unique fingerprint.

    Cite this