Paper by Erik D. Demaine

Reference:

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.

BibTeX

@InProceedings{Movement_SODA2007,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi and
                   Hamid Mahini and Amin S. Sayedi-Roshkhar and
                   Shayan Oveisgharan and Morteza Zadimoghaddam},
  TITLE         = {Minimizing Movement},
  BOOKTITLE     = {Proceedings of the 18th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2007)},
  bookurl       = {http://www.siam.org/meetings/da07/},
  ADDRESS       = {New Orleans, Louisiana},
  MONTH         = {January 7--9},
  YEAR          = 2007,
  PAGES         = {258--267},

  papers        = {Movement_TAlg},
  dblp          = {https://dblp.org/rec/conf/soda/DemaineHMSOZ07},
  ee            = {https://dl.acm.org/doi/10.5555/1283383.1283411},
  comments      = {This paper is also available from <A HREF="https://dl.acm.org/doi/10.5555/1283383.1283411">ACM</A>.},
}

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.

Comments:

This paper is also available from ACM.

Availability:

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)