TY - GEN
T1 - Exploring and triangulating a region by a swarm of robots
AU - Fekete, Sándor P.
AU - Kamphans, Tom
AU - Kröller, Alexander
AU - Mitchell, Joseph S.B.
AU - Schmidt, Christiane
PY - 2011
Y1 - 2011
N2 - We consider online and offline problems related to exploring and surveying a region by a swarm of robots with limited communication range. The minimum relay triangulation problem (MRTP) asks for placing a minimum number of robots, such that their communication graph is a triangulated cover of the region. The maximum area triangulation problem (MATP) aims at finding a placement of n robots such that their communication graph contains a root and forms a triangulated cover of a maximum possible amount of area. Both problems are geometric versions of natural graph optimization problems. The offline version of both problems share a decision problem, which we prove to be NP-hard. For the online version of the MRTP, we give a lower bound of 6/5 for the competitive ratio, and a strategy that achieves a ratio of 3; for different offline versions, we describe polynomial-time approximation schemes. For the MATP we show that no competitive ratio exists for the online problem, and give polynomial-time approximation schemes for offline versions.
AB - We consider online and offline problems related to exploring and surveying a region by a swarm of robots with limited communication range. The minimum relay triangulation problem (MRTP) asks for placing a minimum number of robots, such that their communication graph is a triangulated cover of the region. The maximum area triangulation problem (MATP) aims at finding a placement of n robots such that their communication graph contains a root and forms a triangulated cover of a maximum possible amount of area. Both problems are geometric versions of natural graph optimization problems. The offline version of both problems share a decision problem, which we prove to be NP-hard. For the online version of the MRTP, we give a lower bound of 6/5 for the competitive ratio, and a strategy that achieves a ratio of 3; for different offline versions, we describe polynomial-time approximation schemes. For the MATP we show that no competitive ratio exists for the online problem, and give polynomial-time approximation schemes for offline versions.
UR - https://www.scopus.com/pages/publications/80052364885
U2 - 10.1007/978-3-642-22935-0_18
DO - 10.1007/978-3-642-22935-0_18
M3 - Conference contribution
AN - SCOPUS:80052364885
SN - 9783642229343
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 206
EP - 217
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 -