**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]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.