--- _id: '19724' abstract: - lang: eng text: 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. author: - first_name: Olaf full_name: Bonorden, Olaf last_name: Bonorden - first_name: Bastian full_name: Degener, Bastian last_name: Degener - first_name: Barbara full_name: Kempkes, Barbara last_name: Kempkes - first_name: Peter full_name: Pietrzyk, Peter last_name: Pietrzyk citation: ama: 'Bonorden O, Degener B, Kempkes B, Pietrzyk P. Complexity and Approximation of a Geometric Local Robot Assignment Problem. In: Algorithmic Aspects of Wireless Sensor Networks. Berlin, Heidelberg: Springer; 2009:252-262. doi:10.1007/978-3-642-05434-1_25' apa: 'Bonorden, O., Degener, B., Kempkes, B., & Pietrzyk, P. (2009). Complexity and Approximation of a Geometric Local Robot Assignment Problem. In Algorithmic Aspects of Wireless Sensor Networks (pp. 252–262). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-05434-1_25' bibtex: '@inbook{Bonorden_Degener_Kempkes_Pietrzyk_2009, place={Berlin, Heidelberg}, title={Complexity and Approximation of a Geometric Local Robot Assignment Problem}, DOI={10.1007/978-3-642-05434-1_25}, booktitle={Algorithmic Aspects of Wireless Sensor Networks}, publisher={Springer}, author={Bonorden, Olaf and Degener, Bastian and Kempkes, Barbara and Pietrzyk, Peter}, year={2009}, pages={252–262} }' chicago: 'Bonorden, Olaf, Bastian Degener, Barbara Kempkes, and Peter Pietrzyk. “Complexity and Approximation of a Geometric Local Robot Assignment Problem.” In Algorithmic Aspects of Wireless Sensor Networks, 252–62. Berlin, Heidelberg: Springer, 2009. https://doi.org/10.1007/978-3-642-05434-1_25.' ieee: 'O. Bonorden, B. Degener, B. Kempkes, and P. Pietrzyk, “Complexity and Approximation of a Geometric Local Robot Assignment Problem,” in Algorithmic Aspects of Wireless Sensor Networks, Berlin, Heidelberg: Springer, 2009, pp. 252–262.' mla: Bonorden, Olaf, et al. “Complexity and Approximation of a Geometric Local Robot Assignment Problem.” Algorithmic Aspects of Wireless Sensor Networks, Springer, 2009, pp. 252–62, doi:10.1007/978-3-642-05434-1_25. short: 'O. Bonorden, B. Degener, B. Kempkes, P. Pietrzyk, in: Algorithmic Aspects of Wireless Sensor Networks, Springer, Berlin, Heidelberg, 2009, pp. 252–262.' date_created: 2020-09-28T10:25:34Z date_updated: 2022-01-06T06:54:10Z department: - _id: '63' doi: 10.1007/978-3-642-05434-1_25 language: - iso: eng page: 252-262 place: Berlin, Heidelberg publication: Algorithmic Aspects of Wireless Sensor Networks publication_identifier: isbn: - '9783642054334' - '9783642054341' issn: - 0302-9743 - 1611-3349 publication_status: published publisher: Springer status: public title: Complexity and Approximation of a Geometric Local Robot Assignment Problem type: book_chapter user_id: '15415' year: '2009' ...