Paper by Erik D. Demaine
- Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam, “Minimizing Movement”, in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, January 7–9, 2007, pages 258–267.
We give approximation algorithms and inapproximability results for a class of
movement problems. In general, these problems involve planning the
coordinated motion of a large collection of objects (representing anything
from a robot swarm or firefighter team to map labels or network messages) to
achieve a global property of the network while minimizing the maximum or
average movement. In particular, we consider the goals of achieving
connectivity (undirected and directed), achieving connectivity between a given
pair of vertices, achieving independence (a dispersion problem), and achieving
a perfect matching (with applications to multicasting). This general family
of movement problems encompass an intriguing range of graph and geometric
algorithms, with several real-world applications and a surprising range of
approximability. In some cases, we obtain tight approximation and
inapproximability results using direct techniques (without use of PCP),
assuming just that P ≠ NP.
- The paper is available in PostScript (739k), gzipped PostScript (284k), and PDF (290k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Movement_TAlg (Minimizing Movement)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 21, 2021 by