TY - CHAP
AB - We introduce a geometric multi-robot assignment problem. Robots positioned in a Euclidean space have to be assigned to treasures in such a way that their joint strength is sufficient to unearth a treasure with a given weight. The robots have a limited range and thus can only be assigned to treasures in their proximity. The objective is to unearth as many treasures as possible. We investigate the complexity of several variants of this problem and show whether they are in $\classP$ or are $\classNP$-complete. Furthermore, we provide a distributed and local constant-factor approximation algorithm using constant-factor resource augmentation for the two-dimensional setting with $\bigO(\log^*n)$ communication rounds.
AU - Bonorden, Olaf
AU - Degener, Bastian
AU - Kempkes, Barbara
AU - Pietrzyk, Peter
ID - 19724
SN - 0302-9743
T2 - Algorithmic Aspects of Wireless Sensor Networks
TI - Complexity and Approximation of a Geometric Local Robot Assignment Problem
ER -