---
_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: <i>Algorithmic Aspects of Wireless
    Sensor Networks</i>. Berlin, Heidelberg: Springer; 2009:252-262. doi:<a href="https://doi.org/10.1007/978-3-642-05434-1_25">10.1007/978-3-642-05434-1_25</a>'
  apa: 'Bonorden, O., Degener, B., Kempkes, B., &#38; Pietrzyk, P. (2009). Complexity
    and Approximation of a Geometric Local Robot Assignment Problem. In <i>Algorithmic
    Aspects of Wireless Sensor Networks</i> (pp. 252–262). Berlin, Heidelberg: Springer.
    <a href="https://doi.org/10.1007/978-3-642-05434-1_25">https://doi.org/10.1007/978-3-642-05434-1_25</a>'
  bibtex: '@inbook{Bonorden_Degener_Kempkes_Pietrzyk_2009, place={Berlin, Heidelberg},
    title={Complexity and Approximation of a Geometric Local Robot Assignment Problem},
    DOI={<a href="https://doi.org/10.1007/978-3-642-05434-1_25">10.1007/978-3-642-05434-1_25</a>},
    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 <i>Algorithmic Aspects of Wireless Sensor Networks</i>, 252–62. Berlin, Heidelberg:
    Springer, 2009. <a href="https://doi.org/10.1007/978-3-642-05434-1_25">https://doi.org/10.1007/978-3-642-05434-1_25</a>.'
  ieee: 'O. Bonorden, B. Degener, B. Kempkes, and P. Pietrzyk, “Complexity and Approximation
    of a Geometric Local Robot Assignment Problem,” in <i>Algorithmic Aspects of Wireless
    Sensor Networks</i>, Berlin, Heidelberg: Springer, 2009, pp. 252–262.'
  mla: Bonorden, Olaf, et al. “Complexity and Approximation of a Geometric Local Robot
    Assignment Problem.” <i>Algorithmic Aspects of Wireless Sensor Networks</i>, Springer,
    2009, pp. 252–62, doi:<a href="https://doi.org/10.1007/978-3-642-05434-1_25">10.1007/978-3-642-05434-1_25</a>.
  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'
...