Minimizing Movement

作者：Demaine Erik D^*; Hajiaghayi Mohammadtaghi; Mahini Hamid; Sayedi Roshkhar Amin S; Oveisgharan Shayan; Zadimoghaddam Morteza

来源：ACM Transactions on Algorithms, 2009, 5(3): 30.

DOI：10.1145/1541885.1541891

• Motion planning
• pebble placement
• graphs
• Euclidean plane

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 encompasses 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 not equal NP.

• 出版日期2009-7