Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{Movement_APPROX2011,
  AUTHOR        = {Piotr Berman and Erik D. Demaine and Morteza Zadimoghaddam},
  TITLE         = {{$O(1)$}-Approximations for Maximum Movement Problems},
  BOOKTITLE     = {Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2011)},
  bookurl       = {http://cui.unige.ch/tcs/random-approx/2011/index.php},
  ADDRESS       = {Princeton, New Jersey},
  MONTH         = {August 17--19},
  YEAR          = 2011,
  PAGES         = {62--74},

  length        = {12 pages},
  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1007/978-3-642-22935-0_6},
  dblp          = {https://dblp.org/rec/conf/approx/BermanDZ11},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-642-22935-0_6">SpringerLink</A>.},
}

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]