Paper by Erik D. Demaine

Reference:

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.

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.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 12 pages.

Availability:

The paper is available in PDF (276k).

See information on file formats.

[Google Scholar search]