O(1)-approximations for maximum movement problems

14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. ProceedingsWe 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