Paper by Erik D. Demaine

Reference:

Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam, “Minimizing Movement”, ACM Transactions on Algorithms, volume 5, number 3, July 2009, Article 30.

Abstract:

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.

Length:

The paper is 31 pages.

Availability:

The paper is available in PostScript (1189k), gzipped PostScript (487k), and PDF (403k).

See information on file formats.

[Google Scholar search]

Related papers:

Movement_SODA2007 (Minimizing Movement)