TY - GEN
T1 - O(1)-approximations for maximum movement problems
AU - Berman, Piotr
AU - Demaine, Erik D.
AU - Zadimoghaddam, Morteza
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=80052387133&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80052387133&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22935-0_6
DO - 10.1007/978-3-642-22935-0_6
M3 - Conference contribution
AN - SCOPUS:80052387133
SN - 9783642229343
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 62
EP - 74
BT - Approximation, Randomization, and Combinatorial Optimization
T2 - 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011
Y2 - 17 August 2011 through 19 August 2011
ER -