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
Last updated September 18, 2020 by