Paper by Erik D. Demaine

Piotr Berman, Erik D. Demaine, and Morteza Zadimoghaddam, “O(1)-Approximations for Maximum Movement Problems”, in Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2011), Princeton, New Jersey, August 17–19, 2011, pages 62–74.

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.

This paper is also available from SpringerLink.

The paper is 12 pages.

The paper is available in PDF (276k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 16, 2024 by Erik Demaine.