---
_id: '1787'
author:
- first_name: Tim
full_name: Suess, Tim
last_name: Suess
- first_name: Andrew
full_name: Schoenrock, Andrew
last_name: Schoenrock
- first_name: Sebastian
full_name: Meisner, Sebastian
last_name: Meisner
- first_name: Christian
full_name: Plessl, Christian
id: '16153'
last_name: Plessl
orcid: 0000-0001-5728-9982
citation:
ama: 'Suess T, Schoenrock A, Meisner S, Plessl C. Parallel Macro Pipelining on the
Intel SCC Many-Core Computer. In: Proc. Int. Symp. on Parallel and Distributed
Processing Workshops (IPDPSW). IEEE Computer Society; 2013:64-73. doi:10.1109/IPDPSW.2013.136'
apa: Suess, T., Schoenrock, A., Meisner, S., & Plessl, C. (2013). Parallel Macro
Pipelining on the Intel SCC Many-Core Computer. Proc. Int. Symp. on Parallel
and Distributed Processing Workshops (IPDPSW), 64–73. https://doi.org/10.1109/IPDPSW.2013.136
bibtex: '@inproceedings{Suess_Schoenrock_Meisner_Plessl_2013, place={Washington,
DC, USA}, title={Parallel Macro Pipelining on the Intel SCC Many-Core Computer},
DOI={10.1109/IPDPSW.2013.136},
booktitle={Proc. Int. Symp. on Parallel and Distributed Processing Workshops (IPDPSW)},
publisher={IEEE Computer Society}, author={Suess, Tim and Schoenrock, Andrew and
Meisner, Sebastian and Plessl, Christian}, year={2013}, pages={64–73} }'
chicago: 'Suess, Tim, Andrew Schoenrock, Sebastian Meisner, and Christian Plessl.
“Parallel Macro Pipelining on the Intel SCC Many-Core Computer.” In Proc. Int.
Symp. on Parallel and Distributed Processing Workshops (IPDPSW), 64–73. Washington,
DC, USA: IEEE Computer Society, 2013. https://doi.org/10.1109/IPDPSW.2013.136.'
ieee: 'T. Suess, A. Schoenrock, S. Meisner, and C. Plessl, “Parallel Macro Pipelining
on the Intel SCC Many-Core Computer,” in Proc. Int. Symp. on Parallel and Distributed
Processing Workshops (IPDPSW), 2013, pp. 64–73, doi: 10.1109/IPDPSW.2013.136.'
mla: Suess, Tim, et al. “Parallel Macro Pipelining on the Intel SCC Many-Core Computer.”
Proc. Int. Symp. on Parallel and Distributed Processing Workshops (IPDPSW),
IEEE Computer Society, 2013, pp. 64–73, doi:10.1109/IPDPSW.2013.136.
short: 'T. Suess, A. Schoenrock, S. Meisner, C. Plessl, in: Proc. Int. Symp. on
Parallel and Distributed Processing Workshops (IPDPSW), IEEE Computer Society,
Washington, DC, USA, 2013, pp. 64–73.'
date_created: 2018-03-26T14:51:05Z
date_updated: 2023-09-26T13:38:05Z
department:
- _id: '27'
- _id: '518'
- _id: '78'
- _id: '63'
doi: 10.1109/IPDPSW.2013.136
language:
- iso: eng
page: 64-73
place: Washington, DC, USA
project:
- _id: '30'
grant_number: 01|H11004A
name: Enabling Heterogeneous Hardware Acceleration using Novel Programming and Scheduling
Models
publication: Proc. Int. Symp. on Parallel and Distributed Processing Workshops (IPDPSW)
publication_identifier:
isbn:
- 978-0-7695-4979-8
publisher: IEEE Computer Society
quality_controlled: '1'
status: public
title: Parallel Macro Pipelining on the Intel SCC Many-Core Computer
type: conference
user_id: '15278'
year: '2013'
...
---
_id: '20173'
abstract:
- lang: eng
text: This paper investigates the properties required to evolve Artificial Neural
Networks for distributed control in modular robotics, which typically involves
non-linear dynamics and complex interactions in the sensori-motor space. We investigate
the relation between macro-scale properties (such as modularity and regularity)
and micro-scale properties in Neural Network controllers. We show how neurons
capable of multiplicative-like arithmetic operations may increase the performance
of controllers in several ways whenever challenging control problems with non-linear
dynamics are involved. This paper provides evidence that performance and robustness
of evolved controllers can be improved by a combination of carefully chosen micro-
and macro-scale neural network properties.
author:
- first_name: Heiko
full_name: Hamann, Heiko
last_name: Hamann
- first_name: Jürgen
full_name: Stradner, Jürgen
last_name: Stradner
- first_name: Nicolas
full_name: Bredeche, Nicolas
last_name: Bredeche
- first_name: Leo
full_name: Cazenille, Leo
last_name: Cazenille
citation:
ama: 'Hamann H, Stradner J, Bredeche N, Cazenille L. Impact of Neuron Models and
Network Structure on Evolving Modular Robot Neural Network Controllers. In: 14th
Annual Genetic and Evolutionary Computation Conference, GECCO 2012. ACM; 2012:89-96.
doi:10.1145/2330163.2330177'
apa: Hamann, H., Stradner, J., Bredeche, N., & Cazenille, L. (2012). Impact
of Neuron Models and Network Structure on Evolving Modular Robot Neural Network
Controllers. In 14th Annual Genetic and Evolutionary Computation Conference,
GECCO 2012 (pp. 89–96). ACM. https://doi.org/10.1145/2330163.2330177
bibtex: '@inproceedings{Hamann_Stradner_Bredeche_Cazenille_2012, title={Impact of
Neuron Models and Network Structure on Evolving Modular Robot Neural Network Controllers},
DOI={10.1145/2330163.2330177},
booktitle={14th Annual Genetic and Evolutionary Computation Conference, GECCO
2012}, publisher={ACM}, author={Hamann, Heiko and Stradner, Jürgen and Bredeche,
Nicolas and Cazenille, Leo}, year={2012}, pages={89–96} }'
chicago: Hamann, Heiko, Jürgen Stradner, Nicolas Bredeche, and Leo Cazenille. “Impact
of Neuron Models and Network Structure on Evolving Modular Robot Neural Network
Controllers.” In 14th Annual Genetic and Evolutionary Computation Conference,
GECCO 2012, 89–96. ACM, 2012. https://doi.org/10.1145/2330163.2330177.
ieee: H. Hamann, J. Stradner, N. Bredeche, and L. Cazenille, “Impact of Neuron Models
and Network Structure on Evolving Modular Robot Neural Network Controllers,” in
14th Annual Genetic and Evolutionary Computation Conference, GECCO 2012,
2012, pp. 89–96.
mla: Hamann, Heiko, et al. “Impact of Neuron Models and Network Structure on Evolving
Modular Robot Neural Network Controllers.” 14th Annual Genetic and Evolutionary
Computation Conference, GECCO 2012, ACM, 2012, pp. 89–96, doi:10.1145/2330163.2330177.
short: 'H. Hamann, J. Stradner, N. Bredeche, L. Cazenille, in: 14th Annual Genetic
and Evolutionary Computation Conference, GECCO 2012, ACM, 2012, pp. 89–96.'
date_created: 2020-10-22T09:32:13Z
date_updated: 2022-01-06T06:54:21Z
department:
- _id: '63'
- _id: '238'
doi: 10.1145/2330163.2330177
language:
- iso: eng
page: 89-96
publication: 14th Annual Genetic and Evolutionary Computation Conference, GECCO 2012
publisher: ACM
status: public
title: Impact of Neuron Models and Network Structure on Evolving Modular Robot Neural
Network Controllers
type: conference
user_id: '15415'
year: '2012'
...
---
_id: '20174'
abstract:
- lang: eng
text: 'As a contribution to the efforts towards robotic systems of higher flexibility
we present our concept of morphologically dynamic robots. Within the projects
SYMBRION and REPLICATOR, that focus on modular robotics, we have developed bio-inspired
control techniques to achieve new concepts of dynamic, autonomous morphological
structures. We propose three modes of coupling between robot modules: swarm, team,
and organism mode. We demonstrate our concepts along with simple robot experiments.'
author:
- first_name: Heiko
full_name: Hamann, Heiko
last_name: Hamann
- first_name: Thomas
full_name: Schmickl, Thomas
last_name: Schmickl
- first_name: Jürgen
full_name: Stradner, Jürgen
last_name: Stradner
citation:
ama: 'Hamann H, Schmickl T, Stradner J. Towards Morphological Flexibility: Modular
Robotics and Bio-inspired Control. In: Austrian Robotics Workshop (Operational
Programme Slovenia-Austria). ; 2012.'
apa: 'Hamann, H., Schmickl, T., & Stradner, J. (2012). Towards Morphological
Flexibility: Modular Robotics and Bio-inspired Control. In Austrian Robotics
Workshop (Operational Programme Slovenia-Austria).'
bibtex: '@inproceedings{Hamann_Schmickl_Stradner_2012, title={Towards Morphological
Flexibility: Modular Robotics and Bio-inspired Control}, booktitle={Austrian Robotics
Workshop (Operational Programme Slovenia-Austria)}, author={Hamann, Heiko and
Schmickl, Thomas and Stradner, Jürgen}, year={2012} }'
chicago: 'Hamann, Heiko, Thomas Schmickl, and Jürgen Stradner. “Towards Morphological
Flexibility: Modular Robotics and Bio-Inspired Control.” In Austrian Robotics
Workshop (Operational Programme Slovenia-Austria), 2012.'
ieee: 'H. Hamann, T. Schmickl, and J. Stradner, “Towards Morphological Flexibility:
Modular Robotics and Bio-inspired Control,” in Austrian Robotics Workshop (Operational
Programme Slovenia-Austria), 2012.'
mla: 'Hamann, Heiko, et al. “Towards Morphological Flexibility: Modular Robotics
and Bio-Inspired Control.” Austrian Robotics Workshop (Operational Programme
Slovenia-Austria), 2012.'
short: 'H. Hamann, T. Schmickl, J. Stradner, in: Austrian Robotics Workshop (Operational
Programme Slovenia-Austria), 2012.'
date_created: 2020-10-22T09:36:02Z
date_updated: 2022-01-06T06:54:21Z
department:
- _id: '63'
- _id: '238'
language:
- iso: eng
publication: Austrian Robotics Workshop (Operational Programme Slovenia-Austria)
status: public
title: 'Towards Morphological Flexibility: Modular Robotics and Bio-inspired Control'
type: conference
user_id: '15415'
year: '2012'
...
---
_id: '20175'
author:
- first_name: Heiko
full_name: Hamann, Heiko
last_name: Hamann
- first_name: Thomas
full_name: Schmickl, Thomas
last_name: Schmickl
- first_name: Jürgen
full_name: Stradner, Jürgen
last_name: Stradner
- first_name: Karl
full_name: Crailsheim, Karl
last_name: Crailsheim
- first_name: Payam
full_name: Zahadat, Payam
last_name: Zahadat
- first_name: Christoph
full_name: Adami, Christoph
last_name: Adami
- first_name: David M.
full_name: Bryson, David M.
last_name: Bryson
- first_name: Charles
full_name: Ofria, Charles
last_name: Ofria
- first_name: Robert T.
full_name: Pennock, Robert T.
last_name: Pennock
citation:
ama: 'Hamann H, Schmickl T, Stradner J, et al. On-line, On-board Evolution of Reaction-Diffusion
Control for Self-Adaptation. In: Alife XIII. MIT Press; 2012:597-598.'
apa: Hamann, H., Schmickl, T., Stradner, J., Crailsheim, K., Zahadat, P., Adami,
C., … Pennock, R. T. (2012). On-line, On-board Evolution of Reaction-Diffusion
Control for Self-Adaptation. In Alife XIII (pp. 597–598). MIT Press.
bibtex: '@inproceedings{Hamann_Schmickl_Stradner_Crailsheim_Zahadat_Adami_Bryson_Ofria_Pennock_2012,
title={On-line, On-board Evolution of Reaction-Diffusion Control for Self-Adaptation},
booktitle={Alife XIII}, publisher={MIT Press}, author={Hamann, Heiko and Schmickl,
Thomas and Stradner, Jürgen and Crailsheim, Karl and Zahadat, Payam and Adami,
Christoph and Bryson, David M. and Ofria, Charles and Pennock, Robert T.}, year={2012},
pages={597–598} }'
chicago: Hamann, Heiko, Thomas Schmickl, Jürgen Stradner, Karl Crailsheim, Payam
Zahadat, Christoph Adami, David M. Bryson, Charles Ofria, and Robert T. Pennock.
“On-Line, On-Board Evolution of Reaction-Diffusion Control for Self-Adaptation.”
In Alife XIII, 597–98. MIT Press, 2012.
ieee: H. Hamann et al., “On-line, On-board Evolution of Reaction-Diffusion
Control for Self-Adaptation,” in Alife XIII, 2012, pp. 597–598.
mla: Hamann, Heiko, et al. “On-Line, On-Board Evolution of Reaction-Diffusion Control
for Self-Adaptation.” Alife XIII, MIT Press, 2012, pp. 597–98.
short: 'H. Hamann, T. Schmickl, J. Stradner, K. Crailsheim, P. Zahadat, C. Adami,
D.M. Bryson, C. Ofria, R.T. Pennock, in: Alife XIII, MIT Press, 2012, pp. 597–598.'
date_created: 2020-10-22T09:42:43Z
date_updated: 2022-01-06T06:54:21Z
department:
- _id: '63'
- _id: '238'
language:
- iso: eng
page: 597-598
publication: Alife XIII
publisher: MIT Press
status: public
title: On-line, On-board Evolution of Reaction-Diffusion Control for Self-Adaptation
type: conference
user_id: '15415'
year: '2012'
...
---
_id: '20176'
author:
- first_name: Heiko
full_name: Hamann, Heiko
last_name: Hamann
- first_name: Thomas
full_name: Schmickl, Thomas
last_name: Schmickl
- first_name: Karl
full_name: Crailsheim, Karl
last_name: Crailsheim
citation:
ama: Hamann H, Schmickl T, Crailsheim K. Self-organized pattern formation in a swarm
system as a transient phenomenon of non-linear dynamics. Mathematical and Computer
Modelling of Dynamical Systems. 2012;18(1):39-50. doi:10.1080/13873954.2011.601418
apa: Hamann, H., Schmickl, T., & Crailsheim, K. (2012). Self-organized pattern
formation in a swarm system as a transient phenomenon of non-linear dynamics.
Mathematical and Computer Modelling of Dynamical Systems, 18(1),
39–50. https://doi.org/10.1080/13873954.2011.601418
bibtex: '@article{Hamann_Schmickl_Crailsheim_2012, title={Self-organized pattern
formation in a swarm system as a transient phenomenon of non-linear dynamics},
volume={18}, DOI={10.1080/13873954.2011.601418},
number={1}, journal={Mathematical and Computer Modelling of Dynamical Systems},
author={Hamann, Heiko and Schmickl, Thomas and Crailsheim, Karl}, year={2012},
pages={39–50} }'
chicago: 'Hamann, Heiko, Thomas Schmickl, and Karl Crailsheim. “Self-Organized Pattern
Formation in a Swarm System as a Transient Phenomenon of Non-Linear Dynamics.”
Mathematical and Computer Modelling of Dynamical Systems 18, no. 1 (2012):
39–50. https://doi.org/10.1080/13873954.2011.601418.'
ieee: H. Hamann, T. Schmickl, and K. Crailsheim, “Self-organized pattern formation
in a swarm system as a transient phenomenon of non-linear dynamics,” Mathematical
and Computer Modelling of Dynamical Systems, vol. 18, no. 1, pp. 39–50, 2012.
mla: Hamann, Heiko, et al. “Self-Organized Pattern Formation in a Swarm System as
a Transient Phenomenon of Non-Linear Dynamics.” Mathematical and Computer Modelling
of Dynamical Systems, vol. 18, no. 1, 2012, pp. 39–50, doi:10.1080/13873954.2011.601418.
short: H. Hamann, T. Schmickl, K. Crailsheim, Mathematical and Computer Modelling
of Dynamical Systems 18 (2012) 39–50.
date_created: 2020-10-22T09:47:20Z
date_updated: 2022-01-06T06:54:21Z
department:
- _id: '63'
- _id: '238'
doi: 10.1080/13873954.2011.601418
intvolume: ' 18'
issue: '1'
language:
- iso: eng
page: 39-50
publication: Mathematical and Computer Modelling of Dynamical Systems
publication_identifier:
issn:
- 1387-3954
- 1744-5051
publication_status: published
status: public
title: Self-organized pattern formation in a swarm system as a transient phenomenon
of non-linear dynamics
type: journal_article
user_id: '15415'
volume: 18
year: '2012'
...
---
_id: '20177'
abstract:
- lang: eng
text: One of the main challenges in automatic controller synthesis is to develop
methods that can successfully be applied for complex tasks. The difficulty is
increased even more in the case of settings with multiple interacting agents.
We apply the artificial homeostatic hormone system (AHHS) approach, which is inspired
by the signaling network of unicellular organisms, to control a system of several
independently acting agents decentrally. The approach is designed for evaluation-minimal,
artificial evolution in order to be applicable to complex modular robotics scenarios.
The performance of AHHS controllers is compared with neuroevolution of augmenting
topologies (NEAT) in the coupled inverted pendulums benchmark. AHHS controllers
are found to be better for multimodular settings. We analyze the evolved controllers
with regard to the usage of sensory inputs and the emerging oscillations, and
we give a nonlinear dynamics interpretation. The generalization of evolved controllers
to initial conditions far from the original conditions is investigated and found
to be good. Similarly, the performance of controllers scales well even with module
numbers different from the original domain the controller was evolved for. Two
reference implementations of a similar controller approach are reported and shown
to have shortcomings. We discuss the related work and conclude by summarizing
the main contributions of our work.
author:
- first_name: Heiko
full_name: Hamann, Heiko
last_name: Hamann
- first_name: Thomas
full_name: Schmickl, Thomas
last_name: Schmickl
- first_name: Karl
full_name: Crailsheim, Karl
last_name: Crailsheim
citation:
ama: Hamann H, Schmickl T, Crailsheim K. A Hormone-Based Controller for Evaluation-Minimal
Evolution in Decentrally Controlled Systems. Artificial Life. 2012;18(2):165-198.
doi:10.1162/artl_a_00058
apa: Hamann, H., Schmickl, T., & Crailsheim, K. (2012). A Hormone-Based Controller
for Evaluation-Minimal Evolution in Decentrally Controlled Systems. Artificial
Life, 18(2), 165–198. https://doi.org/10.1162/artl_a_00058
bibtex: '@article{Hamann_Schmickl_Crailsheim_2012, title={A Hormone-Based Controller
for Evaluation-Minimal Evolution in Decentrally Controlled Systems}, volume={18},
DOI={10.1162/artl_a_00058},
number={2}, journal={Artificial Life}, author={Hamann, Heiko and Schmickl, Thomas
and Crailsheim, Karl}, year={2012}, pages={165–198} }'
chicago: 'Hamann, Heiko, Thomas Schmickl, and Karl Crailsheim. “A Hormone-Based
Controller for Evaluation-Minimal Evolution in Decentrally Controlled Systems.”
Artificial Life 18, no. 2 (2012): 165–98. https://doi.org/10.1162/artl_a_00058.'
ieee: H. Hamann, T. Schmickl, and K. Crailsheim, “A Hormone-Based Controller for
Evaluation-Minimal Evolution in Decentrally Controlled Systems,” Artificial
Life, vol. 18, no. 2, pp. 165–198, 2012.
mla: Hamann, Heiko, et al. “A Hormone-Based Controller for Evaluation-Minimal Evolution
in Decentrally Controlled Systems.” Artificial Life, vol. 18, no. 2, 2012,
pp. 165–98, doi:10.1162/artl_a_00058.
short: H. Hamann, T. Schmickl, K. Crailsheim, Artificial Life 18 (2012) 165–198.
date_created: 2020-10-22T09:51:39Z
date_updated: 2022-01-06T06:54:21Z
department:
- _id: '63'
- _id: '238'
doi: 10.1162/artl_a_00058
intvolume: ' 18'
issue: '2'
language:
- iso: eng
page: 165-198
publication: Artificial Life
publication_identifier:
issn:
- 1064-5462
- 1530-9185
publication_status: published
status: public
title: A Hormone-Based Controller for Evaluation-Minimal Evolution in Decentrally
Controlled Systems
type: journal_article
user_id: '15415'
volume: 18
year: '2012'
...
---
_id: '20178'
author:
- first_name: Heiko
full_name: Hamann, Heiko
last_name: Hamann
- first_name: Thomas
full_name: Schmickl, Thomas
last_name: Schmickl
- first_name: Heinz
full_name: Wörn, Heinz
last_name: Wörn
- first_name: Karl
full_name: Crailsheim, Karl
last_name: Crailsheim
citation:
ama: Hamann H, Schmickl T, Wörn H, Crailsheim K. Analysis of emergent symmetry breaking
in collective decision making. Neural Computing and Applications. 2012;21(2):207-218.
doi:10.1007/s00521-010-0368-6
apa: Hamann, H., Schmickl, T., Wörn, H., & Crailsheim, K. (2012). Analysis of
emergent symmetry breaking in collective decision making. Neural Computing
and Applications, 21(2), 207–218. https://doi.org/10.1007/s00521-010-0368-6
bibtex: '@article{Hamann_Schmickl_Wörn_Crailsheim_2012, title={Analysis of emergent
symmetry breaking in collective decision making}, volume={21}, DOI={10.1007/s00521-010-0368-6},
number={2}, journal={Neural Computing and Applications}, author={Hamann, Heiko
and Schmickl, Thomas and Wörn, Heinz and Crailsheim, Karl}, year={2012}, pages={207–218}
}'
chicago: 'Hamann, Heiko, Thomas Schmickl, Heinz Wörn, and Karl Crailsheim. “Analysis
of Emergent Symmetry Breaking in Collective Decision Making.” Neural Computing
and Applications 21, no. 2 (2012): 207–18. https://doi.org/10.1007/s00521-010-0368-6.'
ieee: H. Hamann, T. Schmickl, H. Wörn, and K. Crailsheim, “Analysis of emergent
symmetry breaking in collective decision making,” Neural Computing and Applications,
vol. 21, no. 2, pp. 207–218, 2012.
mla: Hamann, Heiko, et al. “Analysis of Emergent Symmetry Breaking in Collective
Decision Making.” Neural Computing and Applications, vol. 21, no. 2, 2012,
pp. 207–18, doi:10.1007/s00521-010-0368-6.
short: H. Hamann, T. Schmickl, H. Wörn, K. Crailsheim, Neural Computing and Applications
21 (2012) 207–218.
date_created: 2020-10-22T09:56:20Z
date_updated: 2022-01-06T06:54:21Z
department:
- _id: '63'
- _id: '238'
doi: 10.1007/s00521-010-0368-6
intvolume: ' 21'
issue: '2'
language:
- iso: eng
page: 207-218
publication: Neural Computing and Applications
publication_identifier:
issn:
- 0941-0643
- 1433-3058
publication_status: published
status: public
title: Analysis of emergent symmetry breaking in collective decision making
type: journal_article
user_id: '15415'
volume: 21
year: '2012'
...
---
_id: '20179'
author:
- first_name: Heiko
full_name: Hamann, Heiko
last_name: Hamann
- first_name: Andreas
full_name: Engelbrecht, Andreas
last_name: Engelbrecht
- first_name: Mauro
full_name: Birattari, Mauro
last_name: Birattari
- first_name: Marco
full_name: Dorigo, Marco
last_name: Dorigo
- first_name: Christian
full_name: Blum, Christian
last_name: Blum
- first_name: Thomas
full_name: Stuetzle, Thomas
last_name: Stuetzle
- first_name: Anders Lyhne
full_name: Christensen, Anders Lyhne
last_name: Christensen
- first_name: Roderich
full_name: Gross, Roderich
last_name: Gross
citation:
ama: 'Hamann H, Engelbrecht A, Birattari M, et al. Towards Swarm Calculus: Universal
Properties of Swarm Performance and Collective Decisions. In: Swarm Intelligence:
8th International Conference, ANTS 2012. Vol 7461. Berlin, Heidelberg: Springer;
2012:168-179. doi:10.1007/978-3-642-32650-9_15'
apa: 'Hamann, H., Engelbrecht, A., Birattari, M., Dorigo, M., Blum, C., Stuetzle,
T., … Gross, R. (2012). Towards Swarm Calculus: Universal Properties of Swarm
Performance and Collective Decisions. In Swarm Intelligence: 8th International
Conference, ANTS 2012 (Vol. 7461, pp. 168–179). Berlin, Heidelberg: Springer.
https://doi.org/10.1007/978-3-642-32650-9_15'
bibtex: '@inproceedings{Hamann_Engelbrecht_Birattari_Dorigo_Blum_Stuetzle_Christensen_Gross_2012,
place={Berlin, Heidelberg}, title={Towards Swarm Calculus: Universal Properties
of Swarm Performance and Collective Decisions}, volume={7461}, DOI={10.1007/978-3-642-32650-9_15},
booktitle={Swarm Intelligence: 8th International Conference, ANTS 2012}, publisher={Springer},
author={Hamann, Heiko and Engelbrecht, Andreas and Birattari, Mauro and Dorigo,
Marco and Blum, Christian and Stuetzle, Thomas and Christensen, Anders Lyhne and
Gross, Roderich}, year={2012}, pages={168–179} }'
chicago: 'Hamann, Heiko, Andreas Engelbrecht, Mauro Birattari, Marco Dorigo, Christian
Blum, Thomas Stuetzle, Anders Lyhne Christensen, and Roderich Gross. “Towards
Swarm Calculus: Universal Properties of Swarm Performance and Collective Decisions.”
In Swarm Intelligence: 8th International Conference, ANTS 2012, 7461:168–79.
Berlin, Heidelberg: Springer, 2012. https://doi.org/10.1007/978-3-642-32650-9_15.'
ieee: 'H. Hamann et al., “Towards Swarm Calculus: Universal Properties of
Swarm Performance and Collective Decisions,” in Swarm Intelligence: 8th International
Conference, ANTS 2012, 2012, vol. 7461, pp. 168–179.'
mla: 'Hamann, Heiko, et al. “Towards Swarm Calculus: Universal Properties of Swarm
Performance and Collective Decisions.” Swarm Intelligence: 8th International
Conference, ANTS 2012, vol. 7461, Springer, 2012, pp. 168–79, doi:10.1007/978-3-642-32650-9_15.'
short: 'H. Hamann, A. Engelbrecht, M. Birattari, M. Dorigo, C. Blum, T. Stuetzle,
A.L. Christensen, R. Gross, in: Swarm Intelligence: 8th International Conference,
ANTS 2012, Springer, Berlin, Heidelberg, 2012, pp. 168–179.'
date_created: 2020-10-22T10:00:11Z
date_updated: 2022-01-06T06:54:21Z
department:
- _id: '63'
- _id: '238'
doi: 10.1007/978-3-642-32650-9_15
intvolume: ' 7461'
language:
- iso: eng
page: 168-179
place: Berlin, Heidelberg
publication: 'Swarm Intelligence: 8th International Conference, ANTS 2012'
publication_identifier:
isbn:
- '9783642326493'
- '9783642326509'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer
status: public
title: 'Towards Swarm Calculus: Universal Properties of Swarm Performance and Collective
Decisions'
type: conference
user_id: '15415'
volume: 7461
year: '2012'
...
---
_id: '17664'
author:
- first_name: Reuven
full_name: Cohen, Reuven
last_name: Cohen
- first_name: Ilia
full_name: Nudelman, Ilia
last_name: Nudelman
- first_name: Gleb
full_name: Polevoy, Gleb
id: '83983'
last_name: Polevoy
citation:
ama: 'Cohen R, Nudelman I, Polevoy G. On the Admission of Dependent Flows in Powerful
Sensor Networks. In: Infocom’2012, Orlando, Florida. ; 2012.'
apa: Cohen, R., Nudelman, I., & Polevoy, G. (2012). On the Admission of Dependent
Flows in Powerful Sensor Networks. In Infocom’2012, Orlando, Florida.
bibtex: '@inproceedings{Cohen_Nudelman_Polevoy_2012, title={On the Admission of
Dependent Flows in Powerful Sensor Networks}, booktitle={Infocom’2012, Orlando,
Florida}, author={Cohen, Reuven and Nudelman, Ilia and Polevoy, Gleb}, year={2012}
}'
chicago: Cohen, Reuven, Ilia Nudelman, and Gleb Polevoy. “On the Admission of Dependent
Flows in Powerful Sensor Networks.” In Infocom’2012, Orlando, Florida,
2012.
ieee: R. Cohen, I. Nudelman, and G. Polevoy, “On the Admission of Dependent Flows
in Powerful Sensor Networks,” in Infocom’2012, Orlando, Florida, 2012.
mla: Cohen, Reuven, et al. “On the Admission of Dependent Flows in Powerful Sensor
Networks.” Infocom’2012, Orlando, Florida, 2012.
short: 'R. Cohen, I. Nudelman, G. Polevoy, in: Infocom’2012, Orlando, Florida, 2012.'
date_created: 2020-08-06T15:22:24Z
date_updated: 2022-01-06T06:53:16Z
department:
- _id: '63'
- _id: '541'
extern: '1'
language:
- iso: eng
publication: Infocom'2012, Orlando, Florida
status: public
title: On the Admission of Dependent Flows in Powerful Sensor Networks
type: conference
user_id: '83983'
year: '2012'
...
---
_id: '579'
abstract:
- lang: eng
text: A left-to-right maximum in a sequence of n numbers s_1, …, s_n is a number
that is strictly larger than all preceding numbers. In this article we present
a smoothed analysis of the number of left-to-right maxima in the presence of additive
random noise. We show that for every sequence of n numbers s_i ∈ [0,1] that are
perturbed by uniform noise from the interval [-ε,ε], the expected number of left-to-right
maxima is Θ(&sqrt;n/ε + log n) for ε>1/n. For Gaussian noise with standard deviation
σ we obtain a bound of O((log3/2 n)/σ + log n).We apply our results to the analysis
of the smoothed height of binary search trees and the smoothed number of comparisons
in the quicksort algorithm and prove bounds of Θ(&sqrt;n/ε + log n) and Θ(n/ε+1&sqrt;n/ε
+ n log n), respectively, for uniform random noise from the interval [-ε,ε]. Our
results can also be applied to bound the smoothed number of points on a convex
hull of points in the two-dimensional plane and to smoothed motion complexity,
a concept we describe in this article. We bound how often one needs to update
a data structure storing the smallest axis-aligned box enclosing a set of points
moving in d-dimensional space.
author:
- first_name: Valentina
full_name: Damerow, Valentina
last_name: Damerow
- first_name: Bodo
full_name: Manthey, Bodo
last_name: Manthey
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
- first_name: Till
full_name: Tantau, Till
last_name: Tantau
citation:
ama: Damerow V, Manthey B, Meyer auf der Heide F, et al. Smoothed analysis of left-to-right
maxima with applications. Transactions on Algorithms. 2012;(3):30. doi:10.1145/2229163.2229174
apa: Damerow, V., Manthey, B., Meyer auf der Heide, F., Räcke, H., Scheideler, C.,
Sohler, C., & Tantau, T. (2012). Smoothed analysis of left-to-right maxima
with applications. Transactions on Algorithms, (3), 30. https://doi.org/10.1145/2229163.2229174
bibtex: '@article{Damerow_Manthey_Meyer auf der Heide_Räcke_Scheideler_Sohler_Tantau_2012,
title={Smoothed analysis of left-to-right maxima with applications}, DOI={10.1145/2229163.2229174},
number={3}, journal={Transactions on Algorithms}, publisher={ACM}, author={Damerow,
Valentina and Manthey, Bodo and Meyer auf der Heide, Friedhelm and Räcke, Harald
and Scheideler, Christian and Sohler, Christian and Tantau, Till}, year={2012},
pages={30} }'
chicago: 'Damerow, Valentina, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald
Räcke, Christian Scheideler, Christian Sohler, and Till Tantau. “Smoothed Analysis
of Left-to-Right Maxima with Applications.” Transactions on Algorithms,
no. 3 (2012): 30. https://doi.org/10.1145/2229163.2229174.'
ieee: V. Damerow et al., “Smoothed analysis of left-to-right maxima with
applications,” Transactions on Algorithms, no. 3, p. 30, 2012.
mla: Damerow, Valentina, et al. “Smoothed Analysis of Left-to-Right Maxima with
Applications.” Transactions on Algorithms, no. 3, ACM, 2012, p. 30, doi:10.1145/2229163.2229174.
short: V. Damerow, B. Manthey, F. Meyer auf der Heide, H. Räcke, C. Scheideler,
C. Sohler, T. Tantau, Transactions on Algorithms (2012) 30.
date_created: 2017-10-17T12:42:45Z
date_updated: 2022-01-06T07:02:41Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
doi: 10.1145/2229163.2229174
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T09:04:58Z
date_updated: 2018-03-15T09:04:58Z
file_id: '1266'
file_name: 579-a30-damerow.pdf
file_size: 329282
relation: main_file
success: 1
file_date_updated: 2018-03-15T09:04:58Z
has_accepted_license: '1'
issue: '3'
page: '30'
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Transactions on Algorithms
publisher: ACM
status: public
title: Smoothed analysis of left-to-right maxima with applications
type: journal_article
user_id: '477'
year: '2012'
...
---
_id: '580'
abstract:
- lang: eng
text: We present and study a new model for energy-aware and profit-oriented scheduling
on a single processor.The processor features dynamic speed scaling as well as
suspension to a sleep mode.Jobs arrive over time, are preemptable, and have different
sizes, values, and deadlines.On the arrival of a new job, the scheduler may either
accept or reject the job.Accepted jobs need a certain energy investment to be
finished in time, while rejected jobs cause costs equal to their values.Here,
power consumption at speed $s$ is given by $P(s)=s^{\alpha}+\beta$ and the energy
investment is power integrated over time.Additionally, the scheduler may decide
to suspend the processor to a sleep mode in which no energy is consumed, though
awaking entails fixed transition costs $\gamma$.The objective is to minimize the
total value of rejected jobs plus the total energy.Our model combines aspects
from advanced energy conservation techniques (namely speed scaling and sleep states)
and profit-oriented scheduling models.We show that \emph{rejection-oblivious}
schedulers (whose rejection decisions are not based on former decisions) have
– in contrast to the model without sleep states – an unbounded competitive ratio.It
turns out that the jobs' value densities (the ratio between a job's value and
its work) are crucial for the performance of such schedulers.We give an algorithm
whose competitiveness nearly matches the lower bound w.r.t\text{.} the maximum
value density.If the maximum value density is not too large, the competitiveness
becomes $\alpha^{\alpha}+2e\alpha$.Also, we show that it suffices to restrict
the value density of low-value jobs only.Using a technique from \cite{Chan:2010}
we transfer our results to processors with a fixed maximum speed.
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Fredrik
full_name: Mallmann Trenn, Fredrik
last_name: Mallmann Trenn
citation:
ama: 'Cord-Landwehr A, Kling P, Mallmann Trenn F. Slow Down & Sleep for Profit
in Online Deadline Scheduling. In: Even G, Rawitz D, eds. Proceedings of the
1st Mediterranean Conference on Algorithms (MedAlg). LNCS. ; 2012:218-231.
doi:10.1007/978-3-642-34862-4_17'
apa: Cord-Landwehr, A., Kling, P., & Mallmann Trenn, F. (2012). Slow Down &
Sleep for Profit in Online Deadline Scheduling. In G. Even & D. Rawitz (Eds.),
Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)
(pp. 218–231). https://doi.org/10.1007/978-3-642-34862-4_17
bibtex: '@inproceedings{Cord-Landwehr_Kling_Mallmann Trenn_2012, series={LNCS},
title={Slow Down & Sleep for Profit in Online Deadline Scheduling}, DOI={10.1007/978-3-642-34862-4_17},
booktitle={Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)},
author={Cord-Landwehr, Andreas and Kling, Peter and Mallmann Trenn, Fredrik},
editor={Even, Guy and Rawitz, DrorEditors}, year={2012}, pages={218–231}, collection={LNCS}
}'
chicago: Cord-Landwehr, Andreas, Peter Kling, and Fredrik Mallmann Trenn. “Slow
Down & Sleep for Profit in Online Deadline Scheduling.” In Proceedings
of the 1st Mediterranean Conference on Algorithms (MedAlg), edited by Guy
Even and Dror Rawitz, 218–31. LNCS, 2012. https://doi.org/10.1007/978-3-642-34862-4_17.
ieee: A. Cord-Landwehr, P. Kling, and F. Mallmann Trenn, “Slow Down & Sleep
for Profit in Online Deadline Scheduling,” in Proceedings of the 1st Mediterranean
Conference on Algorithms (MedAlg), 2012, pp. 218–231.
mla: Cord-Landwehr, Andreas, et al. “Slow Down & Sleep for Profit in Online
Deadline Scheduling.” Proceedings of the 1st Mediterranean Conference on Algorithms
(MedAlg), edited by Guy Even and Dror Rawitz, 2012, pp. 218–31, doi:10.1007/978-3-642-34862-4_17.
short: 'A. Cord-Landwehr, P. Kling, F. Mallmann Trenn, in: G. Even, D. Rawitz (Eds.),
Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), 2012,
pp. 218–231.'
date_created: 2017-10-17T12:42:45Z
date_updated: 2022-01-06T07:02:42Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-34862-4_17
editor:
- first_name: Guy
full_name: Even, Guy
last_name: Even
- first_name: Dror
full_name: Rawitz, Dror
last_name: Rawitz
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T09:03:39Z
date_updated: 2018-03-15T09:03:39Z
file_id: '1265'
file_name: 580-P._Kling__F._Mallmann-Trenn__A._Cord-Landwehr_-_Slow_Down___Sleep_for_Profit_in_Online_Deadline_Scheduling.pdf
file_size: 325939
relation: main_file
success: 1
file_date_updated: 2018-03-15T09:03:39Z
has_accepted_license: '1'
language:
- iso: eng
page: 218-231
project:
- _id: '1'
name: SFB 901
- _id: '14'
name: SFB 901 - Subprojekt C2
- _id: '16'
name: SFB 901 - Subproject C4
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)
series_title: LNCS
status: public
title: Slow Down & Sleep for Profit in Online Deadline Scheduling
type: conference
user_id: '477'
year: '2012'
...
---
_id: '581'
abstract:
- lang: eng
text: 'Nanoparticles are getting more and more in the focus of the scientic community
since the potential for the development of very small particles interacting with
each other and completing medical and other tasks is getting bigger year by year.
In this work we introduce a distributed local algorithm for arranging a set of
nanoparticles on the discrete plane into specic geometric shapes, for instance
a rectangle. The concept of a particle we use can be seen as a simple mobile robot
with the following restrictions: it can only view the state of robots it is physically
connected to, is anonymous, has only a constant size memory, can only move by
using other particles as an anchor point on which it pulls itself alongside, and
it operates in Look-Compute-Move cycles. The main result of this work is the presentation
of a random distributed local algorithm which transforms any given connected set
of particles into a particular geometric shape. As an example we provide a version
of this algorithm for forming a rectangle with an arbitrary predened aspect ratio.
To the best of our knowledge this is the rst work that considers arrangement problems
for these types of robots.'
author:
- first_name: Maximilian
full_name: Drees, Maximilian
last_name: Drees
- first_name: Martina
full_name: 'Hüllmann (married name: Eikel), Martina'
last_name: 'Hüllmann (married name: Eikel)'
- first_name: Andreas
full_name: Koutsopoulos, Andreas
last_name: Koutsopoulos
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Drees M, Hüllmann (married name: Eikel) M, Koutsopoulos A, Scheideler C. Self-Organizing
Particle Systems. In: Proceedings of the 26th IEEE International Parallel and
Distributed Processing Symposium (IPDPS). ; 2012:1272-1283. doi:10.1109/IPDPS.2012.116'
apa: 'Drees, M., Hüllmann (married name: Eikel), M., Koutsopoulos, A., & Scheideler,
C. (2012). Self-Organizing Particle Systems. In Proceedings of the 26th IEEE
International Parallel and Distributed Processing Symposium (IPDPS) (pp. 1272–1283).
https://doi.org/10.1109/IPDPS.2012.116'
bibtex: '@inproceedings{Drees_Hüllmann (married name: Eikel)_Koutsopoulos_Scheideler_2012,
title={Self-Organizing Particle Systems}, DOI={10.1109/IPDPS.2012.116},
booktitle={Proceedings of the 26th IEEE International Parallel and Distributed
Processing Symposium (IPDPS)}, author={Drees, Maximilian and Hüllmann (married
name: Eikel), Martina and Koutsopoulos, Andreas and Scheideler, Christian}, year={2012},
pages={1272–1283} }'
chicago: 'Drees, Maximilian, Martina Hüllmann (married name: Eikel), Andreas Koutsopoulos,
and Christian Scheideler. “Self-Organizing Particle Systems.” In Proceedings
of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS),
1272–83, 2012. https://doi.org/10.1109/IPDPS.2012.116.'
ieee: 'M. Drees, M. Hüllmann (married name: Eikel), A. Koutsopoulos, and C. Scheideler,
“Self-Organizing Particle Systems,” in Proceedings of the 26th IEEE International
Parallel and Distributed Processing Symposium (IPDPS), 2012, pp. 1272–1283.'
mla: Drees, Maximilian, et al. “Self-Organizing Particle Systems.” Proceedings
of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS),
2012, pp. 1272–83, doi:10.1109/IPDPS.2012.116.
short: 'M. Drees, M. Hüllmann (married name: Eikel), A. Koutsopoulos, C. Scheideler,
in: Proceedings of the 26th IEEE International Parallel and Distributed Processing
Symposium (IPDPS), 2012, pp. 1272–1283.'
date_created: 2017-10-17T12:42:45Z
date_updated: 2022-01-06T07:02:42Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
doi: 10.1109/IPDPS.2012.116
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T08:39:33Z
date_updated: 2018-03-15T08:39:33Z
file_id: '1263'
file_name: 581-IPDPS2012-Scheideler_Huellmann.pdf
file_size: 373131
relation: main_file
success: 1
file_date_updated: 2018-03-15T08:39:33Z
has_accepted_license: '1'
language:
- iso: eng
page: 1272-1283
project:
- _id: '1'
name: SFB 901
- _id: '13'
name: SFB 901 - Subprojekt C1
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 26th IEEE International Parallel and Distributed Processing
Symposium (IPDPS)
status: public
title: Self-Organizing Particle Systems
type: conference
user_id: '14955'
year: '2012'
...
---
_id: '601'
abstract:
- lang: eng
text: Wir betrachten eine Gruppe von mobilen, autonomen Robotern in einem ebenen
Gel{\"a}nde. Es gibt keine zentrale Steuerung und die Roboter m{\"u}ssen sich
selbst koordinieren. Zentrale Herausforderung dabei ist, dass jeder Roboter nur
seine unmittelbare Nachbarschaft sieht und auch nur mit Robotern in seiner unmittelbaren
Nachbarschaft kommunizieren kann. Daraus ergeben sich viele algorithmische Fragestellungen.
In dieser Arbeit wird untersucht, unter welchen Voraussetzungen die Roboter sich
auf einem Punkt versammeln bzw. eine Linie zwischen zwei festen Stationen bilden
k{\"o}nnen. Daf{\"u}r werden mehrere Roboter-Strategien in verschiedenen Bewegungsmodellen
vorgestellt. Diese Strategien werden auf ihre Effizienz hin untersucht. Es werden
obere und untere Schranken f{\"u}r die ben{\"o}tigte Anzahl Runden und die Bewegungsdistanz
gezeigt. In einigen F{\"a}llen wird außerdem die ben{\"o}tigte Bewegungsdistanz
mit derjenigen Bewegungsdistanz verglichen, die eine optimale globale Strategie
auf der gleichen Instanz ben{\"o}tigen w{\"u}rde. So werden kompetititve Faktoren
hergeleitet.
author:
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
citation:
ama: Kempkes B. Local Strategies for Robot Formation Problems. Vol 302. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn; 2012.
apa: Kempkes, B. (2012). Local strategies for robot formation problems (Vol.
302). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn.
bibtex: '@book{Kempkes_2012, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn}, title={Local strategies for robot formation problems}, volume={302},
publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Kempkes,
Barbara}, year={2012}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn} }'
chicago: Kempkes, Barbara. Local Strategies for Robot Formation Problems.
Vol. 302. Verlagsschriftenreihe Des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2012.
ieee: B. Kempkes, Local strategies for robot formation problems, vol. 302.
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2012.
mla: Kempkes, Barbara. Local Strategies for Robot Formation Problems. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2012.
short: B. Kempkes, Local Strategies for Robot Formation Problems, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2012.
date_created: 2017-10-17T12:42:49Z
date_updated: 2022-01-06T07:02:50Z
ddc:
- '040'
department:
- _id: '63'
- _id: '26'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T08:16:44Z
date_updated: 2018-03-15T08:16:44Z
file_id: '1252'
file_name: 601-Kempkes-PhD.pdf
file_size: 3805310
relation: main_file
success: 1
file_date_updated: 2018-03-15T08:16:44Z
has_accepted_license: '1'
intvolume: ' 302'
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication_identifier:
isbn:
- 978-3-942647-21-2
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Local strategies for robot formation problems
type: dissertation
user_id: '5786'
volume: 302
year: '2012'
...
---
_id: '619'
abstract:
- lang: eng
text: 'Dynamics in networks is caused by a variety of reasons, like nodes moving
in 2D (or 3D) in multihop cellphone networks, joins and leaves in peer-to-peer
networks, evolution in social networks, and many others. In order to understand
such kinds of dynamics, and to design distributed algorithms that behave well
under dynamics, many ways to model dynamics are introduced and analyzed w.r.t.
correctness and eciency of distributed algorithms. In [16], Kuhn, Lynch, and Oshman
have introduced a very general, worst case type model of dynamics: The edge set
of the network may change arbitrarily from step to step, the only restriction
is that it is connected at all times and the set of nodes does not change. An
extended model demands that a xed connected subnetwork is maintained over each
time interval of length T (T-interval dynamics). They have presented, among others,
algorithms for counting the number of nodes under such general models of dynamics.In
this paper, we generalize their models and algorithms by adding random edge faults,
i.e., we consider fault-prone dynamic networks: We assume that an edge currently
existing may fail to transmit data with some probability p. We rst observe that
strong counting, i.e., each node knows the correct count and stops, is not possible
in a model with random edge faults. Our main two positive results are feasibility
and runtime bounds for weak counting, i.e., stopping is no longer required (but
still a correct count in each node), and for strong counting with an upper bound,
i.e., an upper bound N on n is known to all nodes.'
author:
- first_name: Philipp
full_name: Brandes, Philipp
last_name: Brandes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Brandes P, Meyer auf der Heide F. Distributed Computing in Fault-Prone Dynamic
Networks. In: Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic
Distributed Systems (TADDS). ICPS. ; 2012:9-14. doi:10.1145/2414815.2414818'
apa: Brandes, P., & Meyer auf der Heide, F. (2012). Distributed Computing in
Fault-Prone Dynamic Networks. In Proceedings of the 4th Workshop on Theoretical
Aspects of Dynamic Distributed Systems (TADDS) (pp. 9–14). https://doi.org/10.1145/2414815.2414818
bibtex: '@inproceedings{Brandes_Meyer auf der Heide_2012, series={ICPS}, title={Distributed
Computing in Fault-Prone Dynamic Networks}, DOI={10.1145/2414815.2414818},
booktitle={Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed
Systems (TADDS)}, author={Brandes, Philipp and Meyer auf der Heide, Friedhelm},
year={2012}, pages={9–14}, collection={ICPS} }'
chicago: Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing
in Fault-Prone Dynamic Networks.” In Proceedings of the 4th Workshop on Theoretical
Aspects of Dynamic Distributed Systems (TADDS), 9–14. ICPS, 2012. https://doi.org/10.1145/2414815.2414818.
ieee: P. Brandes and F. Meyer auf der Heide, “Distributed Computing in Fault-Prone
Dynamic Networks,” in Proceedings of the 4th Workshop on Theoretical Aspects
of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14.
mla: Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing
in Fault-Prone Dynamic Networks.” Proceedings of the 4th Workshop on Theoretical
Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14, doi:10.1145/2414815.2414818.
short: 'P. Brandes, F. Meyer auf der Heide, in: Proceedings of the 4th Workshop
on Theoretical Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14.'
date_created: 2017-10-17T12:42:52Z
date_updated: 2022-01-06T07:02:56Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1145/2414815.2414818
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T06:47:15Z
date_updated: 2018-03-15T06:47:15Z
file_id: '1244'
file_name: 619-Brandes_MadHTADDS12_01.pdf
file_size: 346044
relation: main_file
success: 1
file_date_updated: 2018-03-15T06:47:15Z
has_accepted_license: '1'
page: 9-14
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 4th Workshop on Theoretical Aspects of Dynamic Distributed
Systems (TADDS)
series_title: ICPS
status: public
title: Distributed Computing in Fault-Prone Dynamic Networks
type: conference
user_id: '15504'
year: '2012'
...
---
_id: '628'
abstract:
- lang: eng
text: Network creation games model the creation and usage costs of networks formed
by a set of selfish peers.Each peer has the ability to change the network in a
limited way, e.g., by creating or deleting incident links.In doing so, a peer
can reduce its individual communication cost.Typically, these costs are modeled
by the maximum or average distance in the network.We introduce a generalized version
of the basic network creation game (BNCG).In the BNCG (by Alon et al., SPAA 2010),
each peer may replace one of its incident links by a link to an arbitrary peer.This
is done in a selfish way in order to minimize either the maximum or average distance
to all other peers.That is, each peer works towards a network structure that allows
himself to communicate efficiently with all other peers.However, participants
of large networks are seldom interested in all peers.Rather, they want to communicate
efficiently with a small subset only.Our model incorporates these (communication)
interests explicitly.Given peers with interests and a communication network forming
a tree, we prove several results on the structure and quality of equilibria in
our model.We focus on the MAX-version, i.e., each node tries to minimize the maximum
distance to nodes it is interested in, and give an upper bound of O(\sqrt(n))
for the private costs in an equilibrium of n peers.Moreover, we give an equilibrium
for a circular interest graph where a node has private cost Omega(\sqrt(n)), showing
that our bound is tight.This example can be extended such that we get a tight
bound of Theta(\sqrt(n)) for the price of anarchy.For the case of general networks
we show the price of anarchy to be Theta(n).Additionally, we prove an interesting
connection between a maximum independent set in the interest graph and the private
costs of the peers.
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Martina
full_name: 'Huellmann (married name: Eikel), Martina'
last_name: 'Huellmann (married name: Eikel)'
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Alexander
full_name: Setzer, Alexander
id: '11108'
last_name: Setzer
citation:
ama: 'Cord-Landwehr A, Huellmann (married name: Eikel) M, Kling P, Setzer A. Basic
Network Creation Games with Communication Interests. In: Proceedings of the
5th International Symposium on Algorithmic Game Theory (SAGT). LNCS. ; 2012:72--83.
doi:10.1007/978-3-642-33996-7_7'
apa: 'Cord-Landwehr, A., Huellmann (married name: Eikel), M., Kling, P., & Setzer,
A. (2012). Basic Network Creation Games with Communication Interests. In Proceedings
of the 5th International Symposium on Algorithmic Game Theory (SAGT) (pp.
72--83). https://doi.org/10.1007/978-3-642-33996-7_7'
bibtex: '@inproceedings{Cord-Landwehr_Huellmann (married name: Eikel)_Kling_Setzer_2012,
series={LNCS}, title={Basic Network Creation Games with Communication Interests},
DOI={10.1007/978-3-642-33996-7_7},
booktitle={Proceedings of the 5th International Symposium on Algorithmic Game
Theory (SAGT)}, author={Cord-Landwehr, Andreas and Huellmann (married name: Eikel),
Martina and Kling, Peter and Setzer, Alexander}, year={2012}, pages={72--83},
collection={LNCS} }'
chicago: 'Cord-Landwehr, Andreas, Martina Huellmann (married name: Eikel), Peter
Kling, and Alexander Setzer. “Basic Network Creation Games with Communication
Interests.” In Proceedings of the 5th International Symposium on Algorithmic
Game Theory (SAGT), 72--83. LNCS, 2012. https://doi.org/10.1007/978-3-642-33996-7_7.'
ieee: 'A. Cord-Landwehr, M. Huellmann (married name: Eikel), P. Kling, and A. Setzer,
“Basic Network Creation Games with Communication Interests,” in Proceedings
of the 5th International Symposium on Algorithmic Game Theory (SAGT), 2012,
pp. 72--83.'
mla: Cord-Landwehr, Andreas, et al. “Basic Network Creation Games with Communication
Interests.” Proceedings of the 5th International Symposium on Algorithmic Game
Theory (SAGT), 2012, pp. 72--83, doi:10.1007/978-3-642-33996-7_7.
short: 'A. Cord-Landwehr, M. Huellmann (married name: Eikel), P. Kling, A. Setzer,
in: Proceedings of the 5th International Symposium on Algorithmic Game Theory
(SAGT), 2012, pp. 72--83.'
date_created: 2017-10-17T12:42:54Z
date_updated: 2022-01-06T07:02:59Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
doi: 10.1007/978-3-642-33996-7_7
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T06:42:01Z
date_updated: 2018-03-15T06:42:01Z
file_id: '1238'
file_name: 628-FULL_paper_bncs_with_interests.pdf
file_size: 300591
relation: main_file
success: 1
file_date_updated: 2018-03-15T06:42:01Z
has_accepted_license: '1'
language:
- iso: eng
page: 72--83
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 5th International Symposium on Algorithmic Game Theory
(SAGT)
series_title: LNCS
status: public
title: Basic Network Creation Games with Communication Interests
type: conference
user_id: '477'
year: '2012'
...
---
_id: '636'
abstract:
- lang: eng
text: We consider an online facility location problem where clients arrive over
time and their demands have to be served by opening facilities and assigning the
clients to opened facilities. When opening a facility we must choose one of K
different lease types to use. A lease type k has a certain lease length lk. Opening
a facility i using lease type k causes a cost of f k i and ensures that i is open
for the next lk time steps. In addition to costs for opening facilities, we have
to take connection costs ci j into account when assigning a client j to facility
i. We develop and analyze the first online algorithm for this problem that has
a time-independent competitive factor.This variant of the online facility location
problem was introduced by Nagarajan and Williamson [7] and is strongly related
to both the online facility problem by Meyerson [5] and the parking permit problem
by Meyerson [6]. Nagarajan and Williamson gave a 3-approximation algorithm for
the offline problem and an O(Klogn)-competitive algorithm for the online variant.
Here, n denotes the total number of clients arriving over time. We extend their
result by removing the dependency on n (and thereby on the time). In general,
our algorithm is O(lmax log(lmax))-competitive. Here lmax denotes the maximum
lease length. Moreover, we prove that it is O(log2(lmax))-competitive for many
“natural” cases. Such cases include, for example, situations where the number
of clients arriving in each time step does not vary too much, or is non-increasing,
or is polynomially bounded in lmax.
author:
- 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: Peter
full_name: Kling, Peter
last_name: Kling
citation:
ama: 'Meyer auf der Heide F, Pietrzyk P, Kling P. An Algorithm for Facility Leasing.
In: Proceedings of the 19th International Colloquium on Structural Information
& Communication Complexity (SIROCCO). LNCS. ; 2012:61-72. doi:10.1007/978-3-642-31104-8_6'
apa: Meyer auf der Heide, F., Pietrzyk, P., & Kling, P. (2012). An Algorithm
for Facility Leasing. In Proceedings of the 19th International Colloquium on
Structural Information & Communication Complexity (SIROCCO) (pp. 61–72).
https://doi.org/10.1007/978-3-642-31104-8_6
bibtex: '@inproceedings{Meyer auf der Heide_Pietrzyk_Kling_2012, series={LNCS},
title={An Algorithm for Facility Leasing}, DOI={10.1007/978-3-642-31104-8_6},
booktitle={Proceedings of the 19th International Colloquium on Structural Information
& Communication Complexity (SIROCCO)}, author={Meyer auf der Heide, Friedhelm
and Pietrzyk, Peter and Kling, Peter}, year={2012}, pages={61–72}, collection={LNCS}
}'
chicago: Meyer auf der Heide, Friedhelm, Peter Pietrzyk, and Peter Kling. “An Algorithm
for Facility Leasing.” In Proceedings of the 19th International Colloquium
on Structural Information & Communication Complexity (SIROCCO), 61–72.
LNCS, 2012. https://doi.org/10.1007/978-3-642-31104-8_6.
ieee: F. Meyer auf der Heide, P. Pietrzyk, and P. Kling, “An Algorithm for Facility
Leasing,” in Proceedings of the 19th International Colloquium on Structural
Information & Communication Complexity (SIROCCO), 2012, pp. 61–72.
mla: Meyer auf der Heide, Friedhelm, et al. “An Algorithm for Facility Leasing.”
Proceedings of the 19th International Colloquium on Structural Information
& Communication Complexity (SIROCCO), 2012, pp. 61–72, doi:10.1007/978-3-642-31104-8_6.
short: 'F. Meyer auf der Heide, P. Pietrzyk, P. Kling, in: Proceedings of the 19th
International Colloquium on Structural Information & Communication Complexity
(SIROCCO), 2012, pp. 61–72.'
date_created: 2017-10-17T12:42:56Z
date_updated: 2022-01-06T07:03:02Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-31104-8_6
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-14T14:14:21Z
date_updated: 2018-03-14T14:14:21Z
file_id: '1232'
file_name: 636-Online_Facility_Location.pdf
file_size: 173049
relation: main_file
success: 1
file_date_updated: 2018-03-14T14:14:21Z
has_accepted_license: '1'
page: 61-72
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 19th International Colloquium on Structural Information
& Communication Complexity (SIROCCO)
series_title: LNCS
status: public
title: An Algorithm for Facility Leasing
type: conference
user_id: '15504'
year: '2012'
...
---
_id: '638'
author:
- first_name: Fabian
full_name: Eidens, Fabian
id: '25078'
last_name: Eidens
citation:
ama: Eidens F. Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn; 2012.
apa: Eidens, F. (2012). Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn.
bibtex: '@book{Eidens_2012, title={Adaptive Verbindungsstrategien in dynamischen
Suchnetzwerken}, publisher={Universität Paderborn}, author={Eidens, Fabian}, year={2012}
}'
chicago: Eidens, Fabian. Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn, 2012.
ieee: F. Eidens, Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn, 2012.
mla: Eidens, Fabian. Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken.
Universität Paderborn, 2012.
short: F. Eidens, Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken,
Universität Paderborn, 2012.
date_created: 2017-10-17T12:42:56Z
date_updated: 2022-01-06T07:03:03Z
department:
- _id: '63'
language:
- iso: ger
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
title: Adaptive Verbindungsstrategien in dynamischen Suchnetzwerken
type: bachelorsthesis
user_id: '477'
year: '2012'
...
---
_id: '16445'
author:
- 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: 'Kempkes B, Meyer auf der Heide F. Continuous Local Strategies for Robotic
Formation Problems. In: Experimental Algorithms. Berlin, Heidelberg; 2012.
doi:10.1007/978-3-642-30850-5_2'
apa: Kempkes, B., & Meyer auf der Heide, F. (2012). Continuous Local Strategies
for Robotic Formation Problems. In Experimental Algorithms. Berlin, Heidelberg.
https://doi.org/10.1007/978-3-642-30850-5_2
bibtex: '@inbook{Kempkes_Meyer auf der Heide_2012, place={Berlin, Heidelberg}, title={Continuous
Local Strategies for Robotic Formation Problems}, DOI={10.1007/978-3-642-30850-5_2},
booktitle={Experimental Algorithms}, author={Kempkes, Barbara and Meyer auf der
Heide, Friedhelm}, year={2012} }'
chicago: Kempkes, Barbara, and Friedhelm Meyer auf der Heide. “Continuous Local
Strategies for Robotic Formation Problems.” In Experimental Algorithms.
Berlin, Heidelberg, 2012. https://doi.org/10.1007/978-3-642-30850-5_2.
ieee: B. Kempkes and F. Meyer auf der Heide, “Continuous Local Strategies for Robotic
Formation Problems,” in Experimental Algorithms, Berlin, Heidelberg, 2012.
mla: Kempkes, Barbara, and Friedhelm Meyer auf der Heide. “Continuous Local Strategies
for Robotic Formation Problems.” Experimental Algorithms, 2012, doi:10.1007/978-3-642-30850-5_2.
short: 'B. Kempkes, F. Meyer auf der Heide, in: Experimental Algorithms, Berlin,
Heidelberg, 2012.'
date_created: 2020-04-07T06:41:18Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-30850-5_2
language:
- iso: eng
place: Berlin, Heidelberg
publication: Experimental Algorithms
publication_identifier:
isbn:
- '9783642308499'
- '9783642308505'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Continuous Local Strategies for Robotic Formation Problems
type: book_chapter
user_id: '15415'
year: '2012'
...
---
_id: '16446'
author:
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- 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: 'Kempkes B, Kling P, Meyer auf der Heide F. Optimal and competitive runtime
bounds for continuous, local gathering of mobile robots. In: Proceedinbgs of
the 24th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’12.
; 2012. doi:10.1145/2312005.2312009'
apa: Kempkes, B., Kling, P., & Meyer auf der Heide, F. (2012). Optimal and competitive
runtime bounds for continuous, local gathering of mobile robots. In Proceedinbgs
of the 24th ACM symposium on Parallelism in algorithms and architectures - SPAA
’12. https://doi.org/10.1145/2312005.2312009
bibtex: '@inproceedings{Kempkes_Kling_Meyer auf der Heide_2012, title={Optimal and
competitive runtime bounds for continuous, local gathering of mobile robots},
DOI={10.1145/2312005.2312009},
booktitle={Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms
and architectures - SPAA ’12}, author={Kempkes, Barbara and Kling, Peter and Meyer
auf der Heide, Friedhelm}, year={2012} }'
chicago: Kempkes, Barbara, Peter Kling, and Friedhelm Meyer auf der Heide. “Optimal
and Competitive Runtime Bounds for Continuous, Local Gathering of Mobile Robots.”
In Proceedinbgs of the 24th ACM Symposium on Parallelism in Algorithms and
Architectures - SPAA ’12, 2012. https://doi.org/10.1145/2312005.2312009.
ieee: B. Kempkes, P. Kling, and F. Meyer auf der Heide, “Optimal and competitive
runtime bounds for continuous, local gathering of mobile robots,” in Proceedinbgs
of the 24th ACM symposium on Parallelism in algorithms and architectures - SPAA
’12, 2012.
mla: Kempkes, Barbara, et al. “Optimal and Competitive Runtime Bounds for Continuous,
Local Gathering of Mobile Robots.” Proceedinbgs of the 24th ACM Symposium on
Parallelism in Algorithms and Architectures - SPAA ’12, 2012, doi:10.1145/2312005.2312009.
short: 'B. Kempkes, P. Kling, F. Meyer auf der Heide, in: Proceedinbgs of the 24th
ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’12, 2012.'
date_created: 2020-04-07T06:43:11Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1145/2312005.2312009
language:
- iso: eng
publication: Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and
architectures - SPAA '12
publication_identifier:
isbn:
- '9781450312134'
publication_status: published
status: public
title: Optimal and competitive runtime bounds for continuous, local gathering of mobile
robots
type: conference
user_id: '15415'
year: '2012'
...
---
_id: '16448'
author:
- 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: 'Kempkes B, Meyer auf der Heide F. Local, Self-organizing Strategies for Robotic
Formation Problems. In: Algorithms for Sensor Systems. Berlin, Heidelberg;
2012. doi:10.1007/978-3-642-28209-6_2'
apa: Kempkes, B., & Meyer auf der Heide, F. (2012). Local, Self-organizing Strategies
for Robotic Formation Problems. In Algorithms for Sensor Systems. Berlin,
Heidelberg. https://doi.org/10.1007/978-3-642-28209-6_2
bibtex: '@inbook{Kempkes_Meyer auf der Heide_2012, place={Berlin, Heidelberg}, title={Local,
Self-organizing Strategies for Robotic Formation Problems}, DOI={10.1007/978-3-642-28209-6_2},
booktitle={Algorithms for Sensor Systems}, author={Kempkes, Barbara and Meyer
auf der Heide, Friedhelm}, year={2012} }'
chicago: Kempkes, Barbara, and Friedhelm Meyer auf der Heide. “Local, Self-Organizing
Strategies for Robotic Formation Problems.” In Algorithms for Sensor Systems.
Berlin, Heidelberg, 2012. https://doi.org/10.1007/978-3-642-28209-6_2.
ieee: B. Kempkes and F. Meyer auf der Heide, “Local, Self-organizing Strategies
for Robotic Formation Problems,” in Algorithms for Sensor Systems, Berlin,
Heidelberg, 2012.
mla: Kempkes, Barbara, and Friedhelm Meyer auf der Heide. “Local, Self-Organizing
Strategies for Robotic Formation Problems.” Algorithms for Sensor Systems,
2012, doi:10.1007/978-3-642-28209-6_2.
short: 'B. Kempkes, F. Meyer auf der Heide, in: Algorithms for Sensor Systems, Berlin,
Heidelberg, 2012.'
date_created: 2020-04-07T06:51:14Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-28209-6_2
language:
- iso: eng
place: Berlin, Heidelberg
publication: Algorithms for Sensor Systems
publication_identifier:
isbn:
- '9783642282089'
- '9783642282096'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Local, Self-organizing Strategies for Robotic Formation Problems
type: book_chapter
user_id: '15415'
year: '2012'
...