---
_id: '657'
abstract:
- lang: eng
text: 'We present two distributed, constant factor approximation algorithms for
the metric facility location problem. Both algorithms have been designed with
a strong emphasis on applicability in the area of wireless sensor networks: in
order to execute them, each sensor node only requires limited local knowledge
and simple computations. Also, the algorithms can cope with measurement errors
and take into account that communication costs between sensor nodes do not necessarily
increase linearly with the distance, but can be represented by a polynomial. Since
it cannot always be expected that sensor nodes execute algorithms in a synchronized
way, our algorithms are executed in an asynchronous model (but they are still
able to break symmetry that might occur when two neighboring nodes act at exactly
the same time). Furthermore, they can deal with dynamic scenarios: if a node moves,
the solution is updated and the update affects only nodes in the local neighborhood.
Finally, the algorithms are robust in the sense that incorrect behavior of some
nodes during some round will, in the end, still result in a good approximation.
The first algorithm runs in expected O(log_{1+\epsilon} n) communication rounds
and yields a \my^4(1+4\my^2(1+\epsilon)^{1/p})^p approximation, while the second
has a running time of expected O(log^2_{1+\epsilon} n) communication rounds and
an approximation factor of \my^4(1 + 2(1 + \epsilon)^{1/p})^p. Here, \epsilon
> 0 is an arbitrarily small constant, p the exponent of the polynomial representing
the communication costs, and \my the relative measurement error.'
author:
- first_name: Sebastan
full_name: Abshoff, Sebastan
last_name: Abshoff
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- 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: 'Abshoff S, Cord-Landwehr A, Degener B, Kempkes B, Pietrzyk P. Local Approximation
Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware
Sensor Networks. In: Proceedings of the 7th International Symposium on Algorithms
for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS).
LNCS. ; 2011:13-27. doi:10.1007/978-3-642-28209-6_3'
apa: Abshoff, S., Cord-Landwehr, A., Degener, B., Kempkes, B., & Pietrzyk, P.
(2011). Local Approximation Algorithms for the Uncapacitated Metric Facility Location
Problem in Power-Aware Sensor Networks. In Proceedings of the 7th International
Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous
Mobile Entities (ALGOSENSORS) (pp. 13–27). https://doi.org/10.1007/978-3-642-28209-6_3
bibtex: '@inproceedings{Abshoff_Cord-Landwehr_Degener_Kempkes_Pietrzyk_2011, series={LNCS},
title={Local Approximation Algorithms for the Uncapacitated Metric Facility Location
Problem in Power-Aware Sensor Networks}, DOI={10.1007/978-3-642-28209-6_3},
booktitle={Proceedings of the 7th International Symposium on Algorithms for Sensor
Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)},
author={Abshoff, Sebastan and Cord-Landwehr, Andreas and Degener, Bastian and
Kempkes, Barbara and Pietrzyk, Peter}, year={2011}, pages={13–27}, collection={LNCS}
}'
chicago: Abshoff, Sebastan, Andreas Cord-Landwehr, Bastian Degener, Barbara Kempkes,
and Peter Pietrzyk. “Local Approximation Algorithms for the Uncapacitated Metric
Facility Location Problem in Power-Aware Sensor Networks.” In Proceedings of
the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad
Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), 13–27. LNCS, 2011.
https://doi.org/10.1007/978-3-642-28209-6_3.
ieee: S. Abshoff, A. Cord-Landwehr, B. Degener, B. Kempkes, and P. Pietrzyk, “Local
Approximation Algorithms for the Uncapacitated Metric Facility Location Problem
in Power-Aware Sensor Networks,” in Proceedings of the 7th International Symposium
on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile
Entities (ALGOSENSORS), 2011, pp. 13–27.
mla: Abshoff, Sebastan, et al. “Local Approximation Algorithms for the Uncapacitated
Metric Facility Location Problem in Power-Aware Sensor Networks.” Proceedings
of the 7th International Symposium on Algorithms for Sensor Systems, Wireless
Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), 2011, pp. 13–27,
doi:10.1007/978-3-642-28209-6_3.
short: 'S. Abshoff, A. Cord-Landwehr, B. Degener, B. Kempkes, P. Pietrzyk, in: Proceedings
of the 7th International Symposium on Algorithms for Sensor Systems, Wireless
Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), 2011, pp. 13–27.'
date_created: 2017-10-17T12:43:00Z
date_updated: 2022-01-06T07:03:12Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-28209-6_3
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-14T13:48:21Z
date_updated: 2018-03-14T13:48:21Z
file_id: '1219'
file_name: 657-flp_algosensors2011-Cord-Landwehr.pdf
file_size: 454740
relation: main_file
success: 1
file_date_updated: 2018-03-14T13:48:21Z
has_accepted_license: '1'
language:
- iso: eng
page: 13-27
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 7th International Symposium on Algorithms for Sensor
Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)
series_title: LNCS
status: public
title: Local Approximation Algorithms for the Uncapacitated Metric Facility Location
Problem in Power-Aware Sensor Networks
type: conference
user_id: '477'
year: '2011'
...
---
_id: '663'
author:
- first_name: Kamil
full_name: Swierkot, Kamil
last_name: Swierkot
citation:
ama: Swierkot K. Complexity Classes for Local Computation. Universität Paderborn;
2011.
apa: Swierkot, K. (2011). Complexity Classes for Local Computation. Universität
Paderborn.
bibtex: '@book{Swierkot_2011, title={Complexity Classes for Local Computation},
publisher={Universität Paderborn}, author={Swierkot, Kamil}, year={2011} }'
chicago: Swierkot, Kamil. Complexity Classes for Local Computation. Universität
Paderborn, 2011.
ieee: K. Swierkot, Complexity Classes for Local Computation. Universität
Paderborn, 2011.
mla: Swierkot, Kamil. Complexity Classes for Local Computation. Universität
Paderborn, 2011.
short: K. Swierkot, Complexity Classes for Local Computation, Universität Paderborn,
2011.
date_created: 2017-10-17T12:43:01Z
date_updated: 2022-01-06T07:03:13Z
department:
- _id: '63'
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Complexity Classes for Local Computation
type: mastersthesis
user_id: '477'
year: '2011'
...
---
_id: '664'
abstract:
- lang: eng
text: 'Web Computing is a variant of parallel computing where the idle times of
PCs donated by worldwide distributed users are employed to execute parallel programs.
The PUB-Web library developed by us supports this kind of usage of computing resources.
A major problem for the efficient execution of such parallel programs is load
balancing. In the Web Computing context, this problem becomes more difficult because
of the dynamic behavior of the underlying "parallel computer": the set of available
processors (donated PCs) as well as their availability (idle times) change over
time in an unpredictable fashion.In this paper, we experimentally evaluate and
compare load balancing algorithms in this scenario, namely a variant of the well-established
Work Stealing algorithm and strategies based on a heterogeneous version of distributed
hash-tables (DHHTs) introduced recently. In order to run a meaningful experimental
evaluation, we employ, in addition to our Web Computing library PUB-Web, realistic
data sets for the job input streams and for the dynamics of the availability of
the resources.Our experimental evaluations suggest that Work Stealing is the better
strategy if the number of processes ready to run matches the number of available
processors. But a suitable variant of DHHTs outperforms Work Stealing if there
are significantly more processes ready to run than available processors.'
author:
- first_name: Joachim
full_name: Gehweiler, Joachim
last_name: Gehweiler
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Gehweiler J, Kling P, Meyer auf der Heide F. An Experimental Comparison of
Load Balancing Strategies in a Web Computing Environment. In: Proceedings of
the 9th International Conference on Parallel Processing and Applied Mathematics
(PPAM). LNCS. ; 2011:31--40. doi:10.1007/978-3-642-31500-8_4'
apa: Gehweiler, J., Kling, P., & Meyer auf der Heide, F. (2011). An Experimental
Comparison of Load Balancing Strategies in a Web Computing Environment. In Proceedings
of the 9th International Conference on Parallel Processing and Applied Mathematics
(PPAM) (pp. 31--40). https://doi.org/10.1007/978-3-642-31500-8_4
bibtex: '@inproceedings{Gehweiler_Kling_Meyer auf der Heide_2011, series={LNCS},
title={An Experimental Comparison of Load Balancing Strategies in a Web Computing
Environment}, DOI={10.1007/978-3-642-31500-8_4},
booktitle={Proceedings of the 9th International Conference on Parallel Processing
and Applied Mathematics (PPAM)}, author={Gehweiler, Joachim and Kling, Peter and
Meyer auf der Heide, Friedhelm}, year={2011}, pages={31--40}, collection={LNCS}
}'
chicago: Gehweiler, Joachim, Peter Kling, and Friedhelm Meyer auf der Heide. “An
Experimental Comparison of Load Balancing Strategies in a Web Computing Environment.”
In Proceedings of the 9th International Conference on Parallel Processing and
Applied Mathematics (PPAM), 31--40. LNCS, 2011. https://doi.org/10.1007/978-3-642-31500-8_4.
ieee: J. Gehweiler, P. Kling, and F. Meyer auf der Heide, “An Experimental Comparison
of Load Balancing Strategies in a Web Computing Environment,” in Proceedings
of the 9th International Conference on Parallel Processing and Applied Mathematics
(PPAM), 2011, pp. 31--40.
mla: Gehweiler, Joachim, et al. “An Experimental Comparison of Load Balancing Strategies
in a Web Computing Environment.” Proceedings of the 9th International Conference
on Parallel Processing and Applied Mathematics (PPAM), 2011, pp. 31--40, doi:10.1007/978-3-642-31500-8_4.
short: 'J. Gehweiler, P. Kling, F. Meyer auf der Heide, in: Proceedings of the 9th
International Conference on Parallel Processing and Applied Mathematics (PPAM),
2011, pp. 31--40.'
date_created: 2017-10-17T12:43:01Z
date_updated: 2022-01-06T07:03:14Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-31500-8_4
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-14T13:45:57Z
date_updated: 2018-03-14T13:45:57Z
file_id: '1216'
file_name: 664-PPAM11GKM_01.pdf
file_size: 333335
relation: main_file
success: 1
file_date_updated: 2018-03-14T13:45:57Z
has_accepted_license: '1'
page: 31--40
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '14'
name: SFB 901 - Subproject C2
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 9th International Conference on Parallel Processing
and Applied Mathematics (PPAM)
series_title: LNCS
status: public
title: An Experimental Comparison of Load Balancing Strategies in a Web Computing
Environment
type: conference
user_id: '15504'
year: '2011'
...
---
_id: '667'
citation:
ama: Meyer auf der Heide F, Rajaraman R, eds. 23rd Annual ACM Symposium on Parallelism
in Algorithms and Architectures.; 2011. doi:10.1145/1989493
apa: Meyer auf der Heide, F., & Rajaraman, R. (Eds.). (2011). 23rd Annual
ACM Symposium on Parallelism in Algorithms and Architectures. https://doi.org/10.1145/1989493
bibtex: '@book{Meyer auf der Heide_Rajaraman_2011, title={23rd Annual ACM Symposium
on Parallelism in Algorithms and Architectures}, DOI={10.1145/1989493},
year={2011} }'
chicago: Meyer auf der Heide, Friedhelm, and Rajmohan Rajaraman, eds. 23rd Annual
ACM Symposium on Parallelism in Algorithms and Architectures, 2011. https://doi.org/10.1145/1989493.
ieee: F. Meyer auf der Heide and R. Rajaraman, Eds., 23rd Annual ACM Symposium
on Parallelism in Algorithms and Architectures. 2011.
mla: Meyer auf der Heide, Friedhelm, and Rajmohan Rajaraman, editors. 23rd Annual
ACM Symposium on Parallelism in Algorithms and Architectures. 2011, doi:10.1145/1989493.
short: F. Meyer auf der Heide, R. Rajaraman, eds., 23rd Annual ACM Symposium on
Parallelism in Algorithms and Architectures, 2011.
date_created: 2017-10-17T12:43:02Z
date_updated: 2022-01-06T07:03:14Z
department:
- _id: '63'
doi: 10.1145/1989493
editor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: 'Rajmohan '
full_name: 'Rajaraman, Rajmohan '
last_name: Rajaraman
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
status: public
title: 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures
type: conference_editor
user_id: '477'
year: '2011'
...
---
_id: '16410'
abstract:
- lang: eng
text: 'Gathering n mobile robots in one single point in the Euclidean plane is a
widely studied problem from the area of robot formation problems. Classically,
the robots are assumed to have no physical extent, and they are able to share
a position with other robots. We drop these assumptions and investigate a similar
problem for robots with (a spherical) extent: the goal is to gather the robots
as close together as possible. More exactly, we want the robots to form a sphere
with minimum radius around a predefined point. We propose an algorithm for this
problem which synchronously moves the robots towards the center of the sphere
unless they block each other. In this case, if possible, the robots spin around
the center of the sphere. We analyze this algorithm experimentally in the plane.
If R is the distance of the farthest robot to the center of the sphere, the simulations
indicate a runtime which is linear in n and R. Additionally, we prove a theoretic
upper bound for the runtime of O(nR) for a discrete version of the problem. Simulations
also suggest a runtime of O(n + R) for the discrete version.'
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Martina
full_name: Hüllmann, Martina
last_name: Hüllmann
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Alexander
full_name: Klaas, Alexander
last_name: Klaas
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Sven
full_name: Kurras, Sven
last_name: Kurras
- first_name: Marcus
full_name: Märtens, Marcus
last_name: Märtens
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christoph
full_name: Raupach, Christoph
last_name: Raupach
- first_name: Kamil
full_name: Swierkot, Kamil
last_name: Swierkot
- first_name: Daniel
full_name: Warner, Daniel
last_name: Warner
- first_name: Christoph
full_name: Weddemann, Christoph
last_name: Weddemann
- first_name: Daniel
full_name: Wonisch, Daniel
last_name: Wonisch
citation:
ama: 'Cord-Landwehr A, Degener B, Fischer M, et al. Collisionless Gathering of Robots
with an Extent. In: 37th International Conference on Current Trends in Theory
and Practice of Computer Science (SOFSEM 2011). Springer; 2011:178-189. doi:10.1007/978-3-642-18381-2_15'
apa: Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas,
A., … Wonisch, D. (2011). Collisionless Gathering of Robots with an Extent. In
37th International Conference on Current Trends in Theory and Practice of Computer
Science (SOFSEM 2011) (pp. 178–189). Springer. https://doi.org/10.1007/978-3-642-18381-2_15
bibtex: '@inproceedings{Cord-Landwehr_Degener_Fischer_Hüllmann_Kempkes_Klaas_Kling_Kurras_Märtens_Meyer
auf der Heide_et al._2011, title={Collisionless Gathering of Robots with an Extent},
DOI={10.1007/978-3-642-18381-2_15},
number={6543}, booktitle={37th International Conference on Current Trends in Theory
and Practice of Computer Science (SOFSEM 2011)}, publisher={Springer}, author={Cord-Landwehr,
Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes,
Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus
and Meyer auf der Heide, Friedhelm and et al.}, year={2011}, pages={178–189} }'
chicago: Cord-Landwehr, Andreas, Bastian Degener, Matthias Fischer, Martina Hüllmann,
Barbara Kempkes, Alexander Klaas, Peter Kling, et al. “Collisionless Gathering
of Robots with an Extent.” In 37th International Conference on Current Trends
in Theory and Practice of Computer Science (SOFSEM 2011), 178–89. Springer,
2011. https://doi.org/10.1007/978-3-642-18381-2_15.
ieee: A. Cord-Landwehr et al., “Collisionless Gathering of Robots with an
Extent,” in 37th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM 2011), 2011, no. 6543, pp. 178–189.
mla: Cord-Landwehr, Andreas, et al. “Collisionless Gathering of Robots with an Extent.”
37th International Conference on Current Trends in Theory and Practice of Computer
Science (SOFSEM 2011), no. 6543, Springer, 2011, pp. 178–89, doi:10.1007/978-3-642-18381-2_15.
short: 'A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas,
P. Kling, S. Kurras, M. Märtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot,
D. Warner, C. Weddemann, D. Wonisch, in: 37th International Conference on Current
Trends in Theory and Practice of Computer Science (SOFSEM 2011), Springer, 2011,
pp. 178–189.'
date_created: 2020-04-06T07:52:42Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-18381-2_15
issue: '6543'
language:
- iso: eng
page: 178-189
publication: 37th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM 2011)
publication_identifier:
isbn:
- '9783642183805'
- '9783642183812'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer
status: public
title: Collisionless Gathering of Robots with an Extent
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '16412'
author:
- first_name: Joachim
full_name: Gehweiler, Joachim
last_name: Gehweiler
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Gehweiler J, Meyer auf der Heide F. Bin Packing - How Do I Get My Stuff into
the Boxes. In: Algorithms Unplugged. Berlin, Heidelberg; 2011:367-374.
doi:10.1007/978-3-642-15328-0_38'
apa: Gehweiler, J., & Meyer auf der Heide, F. (2011). Bin Packing - How Do I
Get My Stuff into the Boxes. In Algorithms Unplugged (pp. 367–374). Berlin,
Heidelberg. https://doi.org/10.1007/978-3-642-15328-0_38
bibtex: '@inbook{Gehweiler_Meyer auf der Heide_2011, place={Berlin, Heidelberg},
title={Bin Packing - How Do I Get My Stuff into the Boxes}, DOI={10.1007/978-3-642-15328-0_38},
booktitle={Algorithms Unplugged}, author={Gehweiler, Joachim and Meyer auf der
Heide, Friedhelm}, year={2011}, pages={367–374} }'
chicago: Gehweiler, Joachim, and Friedhelm Meyer auf der Heide. “Bin Packing - How
Do I Get My Stuff into the Boxes.” In Algorithms Unplugged, 367–74. Berlin,
Heidelberg, 2011. https://doi.org/10.1007/978-3-642-15328-0_38.
ieee: J. Gehweiler and F. Meyer auf der Heide, “Bin Packing - How Do I Get My Stuff
into the Boxes,” in Algorithms Unplugged, Berlin, Heidelberg, 2011, pp.
367–374.
mla: Gehweiler, Joachim, and Friedhelm Meyer auf der Heide. “Bin Packing - How Do
I Get My Stuff into the Boxes.” Algorithms Unplugged, 2011, pp. 367–74,
doi:10.1007/978-3-642-15328-0_38.
short: 'J. Gehweiler, F. Meyer auf der Heide, in: Algorithms Unplugged, Berlin,
Heidelberg, 2011, pp. 367–374.'
date_created: 2020-04-06T10:10:39Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-15328-0_38
language:
- iso: eng
page: 367-374
place: Berlin, Heidelberg
publication: Algorithms Unplugged
publication_identifier:
isbn:
- '9783642153273'
- '9783642153280'
publication_status: published
status: public
title: Bin Packing - How Do I Get My Stuff into the Boxes
type: book_chapter
user_id: '15415'
year: '2011'
...
---
_id: '16428'
author:
- first_name: Rajmohan
full_name: Rajaraman, Rajmohan
last_name: Rajaraman
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Rajaraman R, Meyer auf der Heide F. Proceedings of the 23rd ACM symposium
on Parallelism in algorithms and architectures - SPAA ’11. In: ; 2011. doi:10.1145/1989493'
apa: Rajaraman, R., & Meyer auf der Heide, F. (2011). Proceedings of the 23rd
ACM symposium on Parallelism in algorithms and architectures - SPAA ’11. https://doi.org/10.1145/1989493
bibtex: '@inproceedings{Rajaraman_Meyer auf der Heide_2011, title={Proceedings of
the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA ’11},
DOI={10.1145/1989493}, author={Rajaraman,
Rajmohan and Meyer auf der Heide, Friedhelm}, year={2011} }'
chicago: Rajaraman, Rajmohan, and Friedhelm Meyer auf der Heide. “Proceedings of
the 23rd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’11,”
2011. https://doi.org/10.1145/1989493.
ieee: R. Rajaraman and F. Meyer auf der Heide, “Proceedings of the 23rd ACM symposium
on Parallelism in algorithms and architectures - SPAA ’11,” 2011.
mla: Rajaraman, Rajmohan, and Friedhelm Meyer auf der Heide. Proceedings of the
23rd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’11.
2011, doi:10.1145/1989493.
short: 'R. Rajaraman, F. Meyer auf der Heide, in: 2011.'
date_created: 2020-04-06T13:48:10Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1145/1989493
language:
- iso: eng
publication_identifier:
isbn:
- '9781450307437'
publication_status: published
status: public
title: Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures
- SPAA '11
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '16447'
author:
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Sándor P.
full_name: Fekete, Sándor P.
last_name: Fekete
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Degener B, Fekete SP, Kempkes B, Meyer auf der Heide F. A survey on relay placement
with runtime and approximation guarantees. Computer Science Review. 2011:57-68.
doi:10.1016/j.cosrev.2010.09.005
apa: Degener, B., Fekete, S. P., Kempkes, B., & Meyer auf der Heide, F. (2011).
A survey on relay placement with runtime and approximation guarantees. Computer
Science Review, 57–68. https://doi.org/10.1016/j.cosrev.2010.09.005
bibtex: '@article{Degener_Fekete_Kempkes_Meyer auf der Heide_2011, title={A survey
on relay placement with runtime and approximation guarantees}, DOI={10.1016/j.cosrev.2010.09.005},
journal={Computer Science Review}, author={Degener, Bastian and Fekete, Sándor
P. and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}, year={2011}, pages={57–68}
}'
chicago: Degener, Bastian, Sándor P. Fekete, Barbara Kempkes, and Friedhelm Meyer
auf der Heide. “A Survey on Relay Placement with Runtime and Approximation Guarantees.”
Computer Science Review, 2011, 57–68. https://doi.org/10.1016/j.cosrev.2010.09.005.
ieee: B. Degener, S. P. Fekete, B. Kempkes, and F. Meyer auf der Heide, “A survey
on relay placement with runtime and approximation guarantees,” Computer Science
Review, pp. 57–68, 2011.
mla: Degener, Bastian, et al. “A Survey on Relay Placement with Runtime and Approximation
Guarantees.” Computer Science Review, 2011, pp. 57–68, doi:10.1016/j.cosrev.2010.09.005.
short: B. Degener, S.P. Fekete, B. Kempkes, F. Meyer auf der Heide, Computer Science
Review (2011) 57–68.
date_created: 2020-04-07T06:46:06Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1016/j.cosrev.2010.09.005
language:
- iso: eng
page: 57-68
publication: Computer Science Review
publication_identifier:
issn:
- 1574-0137
publication_status: published
status: public
title: A survey on relay placement with runtime and approximation guarantees
type: journal_article
user_id: '15415'
year: '2011'
...
---
_id: '16451'
author:
- first_name: Philipp
full_name: Brandes, Philipp
last_name: Brandes
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Brandes P, Degener B, Kempkes B, Meyer auf der Heide F. Energy-efficient strategies
for building short chains of mobile robots locally. In: SIROCCO ’11: Proc.
of the 18th International Colloquium on Structural Information and Communication
Complexity. ; 2011:138-149. doi:10.1016/j.tcs.2012.10.056'
apa: 'Brandes, P., Degener, B., Kempkes, B., & Meyer auf der Heide, F. (2011).
Energy-efficient strategies for building short chains of mobile robots locally.
In SIROCCO ’11: Proc. of the 18th International Colloquium on Structural Information
and Communication Complexity (pp. 138–149). https://doi.org/10.1016/j.tcs.2012.10.056'
bibtex: '@inproceedings{Brandes_Degener_Kempkes_Meyer auf der Heide_2011, title={Energy-efficient
strategies for building short chains of mobile robots locally}, DOI={10.1016/j.tcs.2012.10.056},
booktitle={SIROCCO ’11: Proc. of the 18th International Colloquium on Structural
Information and Communication Complexity}, author={Brandes, Philipp and Degener,
Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}, year={2011},
pages={138–149} }'
chicago: 'Brandes, Philipp, Bastian Degener, Barbara Kempkes, and Friedhelm Meyer
auf der Heide. “Energy-Efficient Strategies for Building Short Chains of Mobile
Robots Locally.” In SIROCCO ’11: Proc. of the 18th International Colloquium
on Structural Information and Communication Complexity, 138–49, 2011. https://doi.org/10.1016/j.tcs.2012.10.056.'
ieee: 'P. Brandes, B. Degener, B. Kempkes, and F. Meyer auf der Heide, “Energy-efficient
strategies for building short chains of mobile robots locally,” in SIROCCO
’11: Proc. of the 18th International Colloquium on Structural Information and
Communication Complexity, 2011, pp. 138–149.'
mla: 'Brandes, Philipp, et al. “Energy-Efficient Strategies for Building Short Chains
of Mobile Robots Locally.” SIROCCO ’11: Proc. of the 18th International Colloquium
on Structural Information and Communication Complexity, 2011, pp. 138–49,
doi:10.1016/j.tcs.2012.10.056.'
short: 'P. Brandes, B. Degener, B. Kempkes, F. Meyer auf der Heide, in: SIROCCO
’11: Proc. of the 18th International Colloquium on Structural Information and
Communication Complexity, 2011, pp. 138–149.'
date_created: 2020-04-07T12:12:23Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1016/j.tcs.2012.10.056
language:
- iso: eng
page: 138-149
publication: 'SIROCCO ''11: Proc. of the 18th International Colloquium on Structural
Information and Communication Complexity'
publication_status: published
status: public
title: Energy-efficient strategies for building short chains of mobile robots locally
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '16453'
author:
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Tobias
full_name: Langner, Tobias
last_name: Langner
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Peter
full_name: Pietrzyk, Peter
last_name: Pietrzyk
- first_name: Roger
full_name: Wattenhofer, Roger
last_name: Wattenhofer
citation:
ama: 'Degener B, Kempkes B, Langner T, Meyer auf der Heide F, Pietrzyk P, Wattenhofer
R. A tight runtime bound for synchronous gathering of autonomous robots with limited
visibility. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms
and Architectures - SPAA ’11. ; 2011. doi:10.1145/1989493.1989515'
apa: Degener, B., Kempkes, B., Langner, T., Meyer auf der Heide, F., Pietrzyk, P.,
& Wattenhofer, R. (2011). A tight runtime bound for synchronous gathering
of autonomous robots with limited visibility. In Proceedings of the 23rd ACM
symposium on Parallelism in algorithms and architectures - SPAA ’11. https://doi.org/10.1145/1989493.1989515
bibtex: '@inproceedings{Degener_Kempkes_Langner_Meyer auf der Heide_Pietrzyk_Wattenhofer_2011,
title={A tight runtime bound for synchronous gathering of autonomous robots with
limited visibility}, DOI={10.1145/1989493.1989515},
booktitle={Proceedings of the 23rd ACM symposium on Parallelism in algorithms
and architectures - SPAA ’11}, author={Degener, Bastian and Kempkes, Barbara and
Langner, Tobias and Meyer auf der Heide, Friedhelm and Pietrzyk, Peter and Wattenhofer,
Roger}, year={2011} }'
chicago: Degener, Bastian, Barbara Kempkes, Tobias Langner, Friedhelm Meyer auf
der Heide, Peter Pietrzyk, and Roger Wattenhofer. “A Tight Runtime Bound for Synchronous
Gathering of Autonomous Robots with Limited Visibility.” In Proceedings of
the 23rd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’11,
2011. https://doi.org/10.1145/1989493.1989515.
ieee: B. Degener, B. Kempkes, T. Langner, F. Meyer auf der Heide, P. Pietrzyk, and
R. Wattenhofer, “A tight runtime bound for synchronous gathering of autonomous
robots with limited visibility,” in Proceedings of the 23rd ACM symposium on
Parallelism in algorithms and architectures - SPAA ’11, 2011.
mla: Degener, Bastian, et al. “A Tight Runtime Bound for Synchronous Gathering of
Autonomous Robots with Limited Visibility.” Proceedings of the 23rd ACM Symposium
on Parallelism in Algorithms and Architectures - SPAA ’11, 2011, doi:10.1145/1989493.1989515.
short: 'B. Degener, B. Kempkes, T. Langner, F. Meyer auf der Heide, P. Pietrzyk,
R. Wattenhofer, in: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms
and Architectures - SPAA ’11, 2011.'
date_created: 2020-04-07T12:31:24Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1145/1989493.1989515
language:
- iso: eng
publication: Proceedings of the 23rd ACM symposium on Parallelism in algorithms and
architectures - SPAA '11
publication_identifier:
isbn:
- '9781450307437'
publication_status: published
status: public
title: A tight runtime bound for synchronous gathering of autonomous robots with limited
visibility
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '16454'
author:
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Kling P, Meyer auf der Heide F. Convergence of local communication chain strategies
via linear transformations. In: Proceedings of the 23rd ACM Symposium on Parallelism
in Algorithms and Architectures - SPAA ’11. ; 2011. doi:10.1145/1989493.1989517'
apa: Kling, P., & Meyer auf der Heide, F. (2011). Convergence of local communication
chain strategies via linear transformations. In Proceedings of the 23rd ACM
symposium on Parallelism in algorithms and architectures - SPAA ’11. https://doi.org/10.1145/1989493.1989517
bibtex: '@inproceedings{Kling_Meyer auf der Heide_2011, title={Convergence of local
communication chain strategies via linear transformations}, DOI={10.1145/1989493.1989517},
booktitle={Proceedings of the 23rd ACM symposium on Parallelism in algorithms
and architectures - SPAA ’11}, author={Kling, Peter and Meyer auf der Heide, Friedhelm},
year={2011} }'
chicago: Kling, Peter, and Friedhelm Meyer auf der Heide. “Convergence of Local
Communication Chain Strategies via Linear Transformations.” In Proceedings
of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA
’11, 2011. https://doi.org/10.1145/1989493.1989517.
ieee: P. Kling and F. Meyer auf der Heide, “Convergence of local communication chain
strategies via linear transformations,” in Proceedings of the 23rd ACM symposium
on Parallelism in algorithms and architectures - SPAA ’11, 2011.
mla: Kling, Peter, and Friedhelm Meyer auf der Heide. “Convergence of Local Communication
Chain Strategies via Linear Transformations.” Proceedings of the 23rd ACM Symposium
on Parallelism in Algorithms and Architectures - SPAA ’11, 2011, doi:10.1145/1989493.1989517.
short: 'P. Kling, F. Meyer auf der Heide, in: Proceedings of the 23rd ACM Symposium
on Parallelism in Algorithms and Architectures - SPAA ’11, 2011.'
date_created: 2020-04-07T12:33:00Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1145/1989493.1989517
language:
- iso: eng
publication: Proceedings of the 23rd ACM symposium on Parallelism in algorithms and
architectures - SPAA '11
publication_identifier:
isbn:
- '9781450307437'
publication_status: published
status: public
title: Convergence of local communication chain strategies via linear transformations
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '16455'
author:
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Degener B, Kempkes B, Meyer auf der Heide F. Building Simple Formations in
Large Societies of Tiny Mobile Robots. Procedia Computer Science. 2011:153-155.
doi:10.1016/j.procs.2011.09.049
apa: Degener, B., Kempkes, B., & Meyer auf der Heide, F. (2011). Building Simple
Formations in Large Societies of Tiny Mobile Robots. Procedia Computer Science,
153–155. https://doi.org/10.1016/j.procs.2011.09.049
bibtex: '@article{Degener_Kempkes_Meyer auf der Heide_2011, title={Building Simple
Formations in Large Societies of Tiny Mobile Robots}, DOI={10.1016/j.procs.2011.09.049},
journal={Procedia Computer Science}, author={Degener, Bastian and Kempkes, Barbara
and Meyer auf der Heide, Friedhelm}, year={2011}, pages={153–155} }'
chicago: Degener, Bastian, Barbara Kempkes, and Friedhelm Meyer auf der Heide. “Building
Simple Formations in Large Societies of Tiny Mobile Robots.” Procedia Computer
Science, 2011, 153–55. https://doi.org/10.1016/j.procs.2011.09.049.
ieee: B. Degener, B. Kempkes, and F. Meyer auf der Heide, “Building Simple Formations
in Large Societies of Tiny Mobile Robots,” Procedia Computer Science, pp.
153–155, 2011.
mla: Degener, Bastian, et al. “Building Simple Formations in Large Societies of
Tiny Mobile Robots.” Procedia Computer Science, 2011, pp. 153–55, doi:10.1016/j.procs.2011.09.049.
short: B. Degener, B. Kempkes, F. Meyer auf der Heide, Procedia Computer Science
(2011) 153–155.
date_created: 2020-04-07T12:35:11Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1016/j.procs.2011.09.049
language:
- iso: eng
page: 153-155
publication: Procedia Computer Science
publication_identifier:
issn:
- 1877-0509
publication_status: published
status: public
title: Building Simple Formations in Large Societies of Tiny Mobile Robots
type: journal_article
user_id: '15415'
year: '2011'
...
---
_id: '16456'
author:
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Degener B, Kempkes B, Meyer auf der Heide F. Energy-Awareness in Self-organising
Robotic Exploration Teams. In: Organic Computing — A Paradigm Shift for Complex
Systems. Basel; 2011. doi:10.1007/978-3-0348-0130-0_35'
apa: Degener, B., Kempkes, B., & Meyer auf der Heide, F. (2011). Energy-Awareness
in Self-organising Robotic Exploration Teams. In Organic Computing — A Paradigm
Shift for Complex Systems. Basel. https://doi.org/10.1007/978-3-0348-0130-0_35
bibtex: '@inbook{Degener_Kempkes_Meyer auf der Heide_2011, place={Basel}, title={Energy-Awareness
in Self-organising Robotic Exploration Teams}, DOI={10.1007/978-3-0348-0130-0_35},
booktitle={Organic Computing — A Paradigm Shift for Complex Systems}, author={Degener,
Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}, year={2011}
}'
chicago: Degener, Bastian, Barbara Kempkes, and Friedhelm Meyer auf der Heide. “Energy-Awareness
in Self-Organising Robotic Exploration Teams.” In Organic Computing — A Paradigm
Shift for Complex Systems. Basel, 2011. https://doi.org/10.1007/978-3-0348-0130-0_35.
ieee: B. Degener, B. Kempkes, and F. Meyer auf der Heide, “Energy-Awareness in Self-organising
Robotic Exploration Teams,” in Organic Computing — A Paradigm Shift for Complex
Systems, Basel, 2011.
mla: Degener, Bastian, et al. “Energy-Awareness in Self-Organising Robotic Exploration
Teams.” Organic Computing — A Paradigm Shift for Complex Systems, 2011,
doi:10.1007/978-3-0348-0130-0_35.
short: 'B. Degener, B. Kempkes, F. Meyer auf der Heide, in: Organic Computing —
A Paradigm Shift for Complex Systems, Basel, 2011.'
date_created: 2020-04-07T12:36:17Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-0348-0130-0_35
language:
- iso: eng
place: Basel
publication: Organic Computing — A Paradigm Shift for Complex Systems
publication_identifier:
isbn:
- '9783034801294'
- '9783034801300'
publication_status: published
status: public
title: Energy-Awareness in Self-organising Robotic Exploration Teams
type: book_chapter
user_id: '15415'
year: '2011'
...
---
_id: '16459'
author:
- first_name: Philipp
full_name: Brandes, Philipp
last_name: Brandes
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Brandes P, Degener B, Kempkes B, Meyer auf der Heide F. Energy-Efficient Strategies
for Building Short Chains of Mobile Robots Locally. In: Structural Information
and Communication Complexity. Berlin, Heidelberg; 2011. doi:10.1007/978-3-642-22212-2_13'
apa: Brandes, P., Degener, B., Kempkes, B., & Meyer auf der Heide, F. (2011).
Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally.
In Structural Information and Communication Complexity. Berlin, Heidelberg.
https://doi.org/10.1007/978-3-642-22212-2_13
bibtex: '@inbook{Brandes_Degener_Kempkes_Meyer auf der Heide_2011, place={Berlin,
Heidelberg}, title={Energy-Efficient Strategies for Building Short Chains of Mobile
Robots Locally}, DOI={10.1007/978-3-642-22212-2_13},
booktitle={Structural Information and Communication Complexity}, author={Brandes,
Philipp and Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm},
year={2011} }'
chicago: Brandes, Philipp, Bastian Degener, Barbara Kempkes, and Friedhelm Meyer
auf der Heide. “Energy-Efficient Strategies for Building Short Chains of Mobile
Robots Locally.” In Structural Information and Communication Complexity.
Berlin, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-22212-2_13.
ieee: P. Brandes, B. Degener, B. Kempkes, and F. Meyer auf der Heide, “Energy-Efficient
Strategies for Building Short Chains of Mobile Robots Locally,” in Structural
Information and Communication Complexity, Berlin, Heidelberg, 2011.
mla: Brandes, Philipp, et al. “Energy-Efficient Strategies for Building Short Chains
of Mobile Robots Locally.” Structural Information and Communication Complexity,
2011, doi:10.1007/978-3-642-22212-2_13.
short: 'P. Brandes, B. Degener, B. Kempkes, F. Meyer auf der Heide, in: Structural
Information and Communication Complexity, Berlin, Heidelberg, 2011.'
date_created: 2020-04-08T06:52:53Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-22212-2_13
language:
- iso: eng
place: Berlin, Heidelberg
publication: Structural Information and Communication Complexity
publication_identifier:
isbn:
- '9783642222115'
- '9783642222122'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally
type: book_chapter
user_id: '15415'
year: '2011'
...
---
_id: '17009'
author:
- first_name: D. Frank
full_name: Hsu, D. Frank
last_name: Hsu
- first_name: Bruce M.
full_name: Magga, Bruce M.
last_name: Magga
- first_name: Howard C. T.
full_name: Ho, Howard C. T.
last_name: Ho
- first_name: Juraj
full_name: Hromkovic, Juraj
last_name: Hromkovic
- first_name: Francis C. M.
full_name: Lau, Francis C. M.
last_name: Lau
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Hsu DF, Magga BM, Ho HCT, Hromkovic J, Lau FCM, Meyer auf der Heide F. EDITORIAL.
Journal of Interconnection Networks. 2011:vii-viii. doi:10.1142/s0219265911002885
apa: Hsu, D. F., Magga, B. M., Ho, H. C. T., Hromkovic, J., Lau, F. C. M., &
Meyer auf der Heide, F. (2011). EDITORIAL. Journal of Interconnection Networks,
vii–viii. https://doi.org/10.1142/s0219265911002885
bibtex: '@article{Hsu_Magga_Ho_Hromkovic_Lau_Meyer auf der Heide_2011, title={EDITORIAL},
DOI={10.1142/s0219265911002885},
journal={Journal of Interconnection Networks}, author={Hsu, D. Frank and Magga,
Bruce M. and Ho, Howard C. T. and Hromkovic, Juraj and Lau, Francis C. M. and
Meyer auf der Heide, Friedhelm}, year={2011}, pages={vii–viii} }'
chicago: Hsu, D. Frank, Bruce M. Magga, Howard C. T. Ho, Juraj Hromkovic, Francis
C. M. Lau, and Friedhelm Meyer auf der Heide. “EDITORIAL.” Journal of Interconnection
Networks, 2011, vii–viii. https://doi.org/10.1142/s0219265911002885.
ieee: D. F. Hsu, B. M. Magga, H. C. T. Ho, J. Hromkovic, F. C. M. Lau, and F. Meyer
auf der Heide, “EDITORIAL,” Journal of Interconnection Networks, pp. vii–viii,
2011.
mla: Hsu, D. Frank, et al. “EDITORIAL.” Journal of Interconnection Networks,
2011, pp. vii–viii, doi:10.1142/s0219265911002885.
short: D.F. Hsu, B.M. Magga, H.C.T. Ho, J. Hromkovic, F.C.M. Lau, F. Meyer auf der
Heide, Journal of Interconnection Networks (2011) vii–viii.
date_created: 2020-05-18T13:35:10Z
date_updated: 2022-01-06T06:53:01Z
department:
- _id: '63'
doi: 10.1142/s0219265911002885
language:
- iso: eng
page: vii-viii
publication: Journal of Interconnection Networks
publication_identifier:
issn:
- 0219-2659
- 1793-6713
publication_status: published
status: public
title: EDITORIAL
type: journal_article
user_id: '15415'
year: '2011'
...
---
_id: '16409'
abstract:
- lang: eng
text: "Given a set of n mobile robots in the d-dimensional Euclidean space, the
goal is to let them converge to a single not predefined point. The challenge is
that the robots are limited in their capabilities. Robots can, upon activation,
compute the positions of all other robots using an individual affine coordinate
system. The robots are indistinguishable, oblivious and may have different affine
coordinate systems. A very general discrete time model assumes that robots are
activated in arbitrary order. Further, the computation of a new target point may
happen much earlier than the movement, so that the movement is based on outdated
information about other robot's positions. Time is measured as the number of rounds,
where a round ends as soon as each robot has moved at least once. In [Cohen, Peleg:
Convergence properties of gravitational algorithms in asynchronous robot systems],
the Center of Gravity is considered as target function, convergence was proven,
and the number of rounds needed for halving the diameter of the convex hull of
the robot's positions was shown to be O(n^2) and Omega(n). We present an easy-to-check
property of target functions that guarantee convergence and yields upper time
bounds. This property intuitively says that when a robot computes a new target
point, this point is significantly within the current axes aligned minimal box
containing all robots. This property holds, e.g., for the above-mentioned target
function, and improves the above O(n^2) to an asymptotically optimal O(n) upper
bound. Our technique also yields a constant time bound for a target function that
requires all robots having identical coordinate axes.\r\n"
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Martina
full_name: Hüllmann, Martina
last_name: Hüllmann
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Alexander
full_name: Klaas, Alexander
last_name: Klaas
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Sven
full_name: Kurras, Sven
last_name: Kurras
- first_name: Marcus
full_name: Märtens, Marcus
last_name: Märtens
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christoph
full_name: Raupach, Christoph
last_name: Raupach
- first_name: Kamil
full_name: Swierkot, Kamil
last_name: Swierkot
- first_name: Daniel
full_name: Warner, Daniel
last_name: Warner
- first_name: Christoph
full_name: Weddemann, Christoph
last_name: Weddemann
- first_name: Daniel
full_name: Wonisch, Daniel
last_name: Wonisch
citation:
ama: 'Cord-Landwehr A, Degener B, Fischer M, et al. A New Approach for Analyzing
Convergence Algorithms for Mobile Robots. In: Automata, Languages and Programming.
Berlin, Heidelberg; 2011. doi:10.1007/978-3-642-22012-8_52'
apa: Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas,
A., … Wonisch, D. (2011). A New Approach for Analyzing Convergence Algorithms
for Mobile Robots. In Automata, Languages and Programming. Berlin, Heidelberg.
https://doi.org/10.1007/978-3-642-22012-8_52
bibtex: '@inbook{Cord-Landwehr_Degener_Fischer_Hüllmann_Kempkes_Klaas_Kling_Kurras_Märtens_Meyer
auf der Heide_et al._2011, place={Berlin, Heidelberg}, title={A New Approach for
Analyzing Convergence Algorithms for Mobile Robots}, DOI={10.1007/978-3-642-22012-8_52},
booktitle={Automata, Languages and Programming}, author={Cord-Landwehr, Andreas
and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes,
Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus
and Meyer auf der Heide, Friedhelm and et al.}, year={2011} }'
chicago: Cord-Landwehr, Andreas, Bastian Degener, Matthias Fischer, Martina Hüllmann,
Barbara Kempkes, Alexander Klaas, Peter Kling, et al. “A New Approach for Analyzing
Convergence Algorithms for Mobile Robots.” In Automata, Languages and Programming.
Berlin, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-22012-8_52.
ieee: A. Cord-Landwehr et al., “A New Approach for Analyzing Convergence
Algorithms for Mobile Robots,” in Automata, Languages and Programming,
Berlin, Heidelberg, 2011.
mla: Cord-Landwehr, Andreas, et al. “A New Approach for Analyzing Convergence Algorithms
for Mobile Robots.” Automata, Languages and Programming, 2011, doi:10.1007/978-3-642-22012-8_52.
short: 'A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas,
P. Kling, S. Kurras, M. Märtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot,
D. Warner, C. Weddemann, D. Wonisch, in: Automata, Languages and Programming,
Berlin, Heidelberg, 2011.'
date_created: 2020-04-06T07:47:55Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-22012-8_52
language:
- iso: eng
place: Berlin, Heidelberg
publication: Automata, Languages and Programming
publication_identifier:
isbn:
- '9783642220111'
- '9783642220128'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: A New Approach for Analyzing Convergence Algorithms for Mobile Robots
type: book_chapter
user_id: '15415'
year: '2011'
...
---
_id: '19678'
author:
- first_name: Patrick
full_name: Briest, Patrick
last_name: Briest
- first_name: Heiko
full_name: Röglin, Heiko
last_name: Röglin
citation:
ama: 'Briest P, Röglin H. The Power of Uncertainty: Bundle-Pricing for Unit-Demand
Customers. In: Workshop on Approximation and Online Algorithms (WAOA).
Vol 6534. Lecture Notes in Computer Science. Springer; 2010. doi:10.1007/978-3-642-18318-8_5'
apa: 'Briest, P., & Röglin, H. (2010). The Power of Uncertainty: Bundle-Pricing
for Unit-Demand Customers. In Workshop on Approximation and Online Algorithms
(WAOA) (Vol. 6534). Springer. https://doi.org/10.1007/978-3-642-18318-8_5'
bibtex: '@inproceedings{Briest_Röglin_2010, series={Lecture Notes in Computer Science},
title={The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers}, volume={6534},
DOI={10.1007/978-3-642-18318-8_5},
booktitle={Workshop on Approximation and Online Algorithms (WAOA)}, publisher={Springer},
author={Briest, Patrick and Röglin, Heiko}, year={2010}, collection={Lecture Notes
in Computer Science} }'
chicago: 'Briest, Patrick, and Heiko Röglin. “The Power of Uncertainty: Bundle-Pricing
for Unit-Demand Customers.” In Workshop on Approximation and Online Algorithms
(WAOA), Vol. 6534. Lecture Notes in Computer Science. Springer, 2010. https://doi.org/10.1007/978-3-642-18318-8_5.'
ieee: 'P. Briest and H. Röglin, “The Power of Uncertainty: Bundle-Pricing for Unit-Demand
Customers,” in Workshop on Approximation and Online Algorithms (WAOA),
2010, vol. 6534.'
mla: 'Briest, Patrick, and Heiko Röglin. “The Power of Uncertainty: Bundle-Pricing
for Unit-Demand Customers.” Workshop on Approximation and Online Algorithms
(WAOA), vol. 6534, Springer, 2010, doi:10.1007/978-3-642-18318-8_5.'
short: 'P. Briest, H. Röglin, in: Workshop on Approximation and Online Algorithms
(WAOA), Springer, 2010.'
date_created: 2020-09-24T14:13:19Z
date_updated: 2022-01-06T06:54:09Z
department:
- _id: '63'
doi: 10.1007/978-3-642-18318-8_5
intvolume: ' 6534'
language:
- iso: eng
publication: Workshop on Approximation and Online Algorithms (WAOA)
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: 'The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers'
type: conference
user_id: '15415'
volume: 6534
year: '2010'
...
---
_id: '19711'
author:
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Peter
full_name: Pietrzyk, Peter
last_name: Pietrzyk
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
citation:
ama: 'Degener B, Pietrzyk P, Kempkes B. A local, distributed constant-factor approximation
algorithm for the dynamic facility location problem . In: International Parallel
& Distributed Processing Symposium (IPDPS). ; 2010. doi:10.1109/IPDPS.2010.5470349'
apa: Degener, B., Pietrzyk, P., & Kempkes, B. (2010). A local, distributed constant-factor
approximation algorithm for the dynamic facility location problem . In International
Parallel & Distributed Processing Symposium (IPDPS). https://doi.org/10.1109/IPDPS.2010.5470349
bibtex: '@inproceedings{Degener_Pietrzyk_Kempkes_2010, title={A local, distributed
constant-factor approximation algorithm for the dynamic facility location problem
}, DOI={10.1109/IPDPS.2010.5470349},
booktitle={International Parallel & Distributed Processing Symposium (IPDPS)},
author={Degener, Bastian and Pietrzyk, Peter and Kempkes, Barbara}, year={2010}
}'
chicago: Degener, Bastian, Peter Pietrzyk, and Barbara Kempkes. “A Local, Distributed
Constant-Factor Approximation Algorithm for the Dynamic Facility Location Problem
.” In International Parallel & Distributed Processing Symposium (IPDPS),
2010. https://doi.org/10.1109/IPDPS.2010.5470349.
ieee: B. Degener, P. Pietrzyk, and B. Kempkes, “A local, distributed constant-factor
approximation algorithm for the dynamic facility location problem ,” in International
Parallel & Distributed Processing Symposium (IPDPS), 2010.
mla: Degener, Bastian, et al. “A Local, Distributed Constant-Factor Approximation
Algorithm for the Dynamic Facility Location Problem .” International Parallel
& Distributed Processing Symposium (IPDPS), 2010, doi:10.1109/IPDPS.2010.5470349.
short: 'B. Degener, P. Pietrzyk, B. Kempkes, in: International Parallel & Distributed
Processing Symposium (IPDPS), 2010.'
date_created: 2020-09-28T08:25:37Z
date_updated: 2022-01-06T06:54:10Z
department:
- _id: '63'
doi: 10.1109/IPDPS.2010.5470349
language:
- iso: eng
publication: International Parallel & Distributed Processing Symposium (IPDPS)
status: public
title: 'A local, distributed constant-factor approximation algorithm for the dynamic
facility location problem '
type: conference
user_id: '15415'
year: '2010'
...
---
_id: '19796'
abstract:
- lang: eng
text: "We introduce the Read-Write-Coding-System (RWC) \x96 a very flexible class
of linear block codes that generate efficient and flexible erasure codes for storage
networks. In particular, given a message x of k symbols and a codeword y of n
symbols, an RW code defines additional parameters k \\leq r,w \\leq n that offer
enhanced possibilities to adjust the fault-tolerance capability of the code. More
precisely, an RWC provides linear $\\left(n,k,d\\right)$-codes that have (a) minimum
distance d=n-r+1 for any two codewords, and (b) for each codeword there exists
a codeword for each other message with distance of at most w. Furthermore, depending
on the values r,w and the code alphabet, different block codes such as parity
codes (e.g. RAID 4/5) or Reed-Solomon (RS) codes (if r=k and thus, w=n) can be
generated. In storage networks in which I/O accesses are very costly and redundancy
is crucial, this flexibility has considerable advantages as r and w can optimally
be adapted to read or write intensive applications; only w symbols must be updated
if the message x changes completely, what is different from other codes which
always need to rewrite y completely as x changes. In this paper, we first state
a tight lower bound and basic conditions for all RW codes. Furthermore, we introduce
special RW codes in which all mentioned parameters are adjustable even online,
that is, those RW codes are adaptive to changing demands. At last, we point out
some useful properties regarding safety and security of the stored data."
author:
- first_name: Mario
full_name: Mense, Mario
last_name: Mense
- first_name: Christian
full_name: Schindelhauer, Christian
last_name: Schindelhauer
citation:
ama: 'Mense M, Schindelhauer C. Read-Write-Codes: An Erasure Resilient Encoding
System for Flexible Reading and Writing in Storage Networks. In: Proceedings
of 11th International Symposium on Stabilization, Safety, and Security of Distributed
Systems. Vol 5873. Lecture Notes in Computer Science. ; 2010:624--639. doi:10.1007/978-3-642-05118-0_43'
apa: 'Mense, M., & Schindelhauer, C. (2010). Read-Write-Codes: An Erasure Resilient
Encoding System for Flexible Reading and Writing in Storage Networks. In Proceedings
of 11th International Symposium on Stabilization, Safety, and Security of Distributed
Systems (Vol. 5873, pp. 624--639). https://doi.org/10.1007/978-3-642-05118-0_43'
bibtex: '@inproceedings{Mense_Schindelhauer_2010, series={Lecture Notes in Computer
Science}, title={Read-Write-Codes: An Erasure Resilient Encoding System for Flexible
Reading and Writing in Storage Networks}, volume={5873}, DOI={10.1007/978-3-642-05118-0_43},
booktitle={Proceedings of 11th International Symposium on Stabilization, Safety,
and Security of Distributed Systems}, author={Mense, Mario and Schindelhauer,
Christian}, year={2010}, pages={624--639}, collection={Lecture Notes in Computer
Science} }'
chicago: 'Mense, Mario, and Christian Schindelhauer. “Read-Write-Codes: An Erasure
Resilient Encoding System for Flexible Reading and Writing in Storage Networks.”
In Proceedings of 11th International Symposium on Stabilization, Safety, and
Security of Distributed Systems, 5873:624--639. Lecture Notes in Computer
Science, 2010. https://doi.org/10.1007/978-3-642-05118-0_43.'
ieee: 'M. Mense and C. Schindelhauer, “Read-Write-Codes: An Erasure Resilient Encoding
System for Flexible Reading and Writing in Storage Networks,” in Proceedings
of 11th International Symposium on Stabilization, Safety, and Security of Distributed
Systems, 2010, vol. 5873, pp. 624--639.'
mla: 'Mense, Mario, and Christian Schindelhauer. “Read-Write-Codes: An Erasure Resilient
Encoding System for Flexible Reading and Writing in Storage Networks.” Proceedings
of 11th International Symposium on Stabilization, Safety, and Security of Distributed
Systems, vol. 5873, 2010, pp. 624--639, doi:10.1007/978-3-642-05118-0_43.'
short: 'M. Mense, C. Schindelhauer, in: Proceedings of 11th International Symposium
on Stabilization, Safety, and Security of Distributed Systems, 2010, pp. 624--639.'
date_created: 2020-09-30T12:12:33Z
date_updated: 2022-01-06T06:54:12Z
department:
- _id: '63'
doi: 10.1007/978-3-642-05118-0_43
intvolume: ' 5873'
language:
- iso: eng
page: 624--639
publication: Proceedings of 11th International Symposium on Stabilization, Safety,
and Security of Distributed Systems
publication_identifier:
isbn:
- '9783642051173'
- '9783642051180'
issn:
- 0302-9743
- 1611-3349
publication_status: published
series_title: Lecture Notes in Computer Science
status: public
title: 'Read-Write-Codes: An Erasure Resilient Encoding System for Flexible Reading
and Writing in Storage Networks'
type: conference
user_id: '15415'
volume: 5873
year: '2010'
...
---
_id: '19824'
abstract:
- lang: eng
text: We present 3nuts, a self-stabilizing peer-to-peer (p2p) network supporting
range queries and adapting the overlay structure to the underlying physical network.
3nuts combines concepts of structured and unstructured p2p networks to overcome
their individual shortcomings while keeping their strengths. This is achieved
by combining self maintaining random networks for robustness, a search tree to
allow range queries, and DHTs for load balancing. Simple handshake operations
with provable guarantees are used for maintenance and self-stabilization. Efficiency
of load balancing, fast data access, and robustness are proven by rigorous analysis.
author:
- first_name: Thomas
full_name: Janson, Thomas
last_name: Janson
- first_name: Peter
full_name: Mahlmann, Peter
last_name: Mahlmann
- first_name: Christian
full_name: Schindelhauer, Christian
last_name: Schindelhauer
citation:
ama: 'Janson T, Mahlmann P, Schindelhauer C. A Self-Stabilizing Locality-Aware Peer-to-Peer
Network Combining Random Networks, Search Trees, and DHTs. In: Proceedings
of the 16th International Conference on Parallel and Distributed Systems.
; 2010. doi:10.1109/icpads.2010.42'
apa: Janson, T., Mahlmann, P., & Schindelhauer, C. (2010). A Self-Stabilizing
Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and
DHTs. In Proceedings of the 16th International Conference on Parallel and Distributed
Systems. https://doi.org/10.1109/icpads.2010.42
bibtex: '@inproceedings{Janson_Mahlmann_Schindelhauer_2010, title={A Self-Stabilizing
Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and
DHTs}, DOI={10.1109/icpads.2010.42},
booktitle={Proceedings of the 16th International Conference on Parallel and Distributed
Systems}, author={Janson, Thomas and Mahlmann, Peter and Schindelhauer, Christian},
year={2010} }'
chicago: Janson, Thomas, Peter Mahlmann, and Christian Schindelhauer. “A Self-Stabilizing
Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and
DHTs.” In Proceedings of the 16th International Conference on Parallel and
Distributed Systems, 2010. https://doi.org/10.1109/icpads.2010.42.
ieee: T. Janson, P. Mahlmann, and C. Schindelhauer, “A Self-Stabilizing Locality-Aware
Peer-to-Peer Network Combining Random Networks, Search Trees, and DHTs,” in Proceedings
of the 16th International Conference on Parallel and Distributed Systems,
2010.
mla: Janson, Thomas, et al. “A Self-Stabilizing Locality-Aware Peer-to-Peer Network
Combining Random Networks, Search Trees, and DHTs.” Proceedings of the 16th
International Conference on Parallel and Distributed Systems, 2010, doi:10.1109/icpads.2010.42.
short: 'T. Janson, P. Mahlmann, C. Schindelhauer, in: Proceedings of the 16th International
Conference on Parallel and Distributed Systems, 2010.'
date_created: 2020-10-01T09:39:13Z
date_updated: 2022-01-06T06:54:13Z
department:
- _id: '63'
doi: 10.1109/icpads.2010.42
language:
- iso: eng
publication: Proceedings of the 16th International Conference on Parallel and Distributed
Systems
publication_identifier:
isbn:
- '9781424497270'
publication_status: published
status: public
title: A Self-Stabilizing Locality-Aware Peer-to-Peer Network Combining Random Networks,
Search Trees, and DHTs
type: conference
user_id: '15415'
year: '2010'
...