---
_id: '507'
abstract:
- lang: eng
text: We study two-party communication in the context of directed dynamic networks
that are controlled by an adaptive adversary. This adversary is able to change
all edges as long as the networks stay strongly-connected in each round. In this
work, we establish a relation between counting the total number of nodes in the
network and the problem of exchanging tokens between two communication partners
which communicate through a dynamic network. We show that the communication problem
for a constant fraction of n tokens in a dynamic network with n nodes is at most
as hard as counting the number of nodes in a dynamic network with at most 4n+3
nodes. For the proof, we construct a family of directed dynamic networks and apply
a lower bound from two-party communication complexity.
author:
- first_name: Sebastian
full_name: Abshoff, Sebastian
last_name: Abshoff
- first_name: Markus
full_name: Benter, Markus
last_name: Benter
- first_name: Manuel
full_name: Malatyali, Manuel
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Abshoff S, Benter M, Malatyali M, Meyer auf der Heide F. On Two-Party Communication
Through Dynamic Networks. In: Proceedings of the 17th International Conference
on Principles of Distributed Systems (OPODIS). LNCS. ; 2013:11-22. doi:10.1007/978-3-319-03850-6_2'
apa: Abshoff, S., Benter, M., Malatyali, M., & Meyer auf der Heide, F. (2013).
On Two-Party Communication Through Dynamic Networks. In Proceedings of the
17th International Conference on Principles of Distributed Systems (OPODIS)
(pp. 11–22). https://doi.org/10.1007/978-3-319-03850-6_2
bibtex: '@inproceedings{Abshoff_Benter_Malatyali_Meyer auf der Heide_2013, series={LNCS},
title={On Two-Party Communication Through Dynamic Networks}, DOI={10.1007/978-3-319-03850-6_2},
booktitle={Proceedings of the 17th International Conference on Principles of Distributed
Systems (OPODIS)}, author={Abshoff, Sebastian and Benter, Markus and Malatyali,
Manuel and Meyer auf der Heide, Friedhelm}, year={2013}, pages={11–22}, collection={LNCS}
}'
chicago: Abshoff, Sebastian, Markus Benter, Manuel Malatyali, and Friedhelm Meyer
auf der Heide. “On Two-Party Communication Through Dynamic Networks.” In Proceedings
of the 17th International Conference on Principles of Distributed Systems (OPODIS),
11–22. LNCS, 2013. https://doi.org/10.1007/978-3-319-03850-6_2.
ieee: S. Abshoff, M. Benter, M. Malatyali, and F. Meyer auf der Heide, “On Two-Party
Communication Through Dynamic Networks,” in Proceedings of the 17th International
Conference on Principles of Distributed Systems (OPODIS), 2013, pp. 11–22.
mla: Abshoff, Sebastian, et al. “On Two-Party Communication Through Dynamic Networks.”
Proceedings of the 17th International Conference on Principles of Distributed
Systems (OPODIS), 2013, pp. 11–22, doi:10.1007/978-3-319-03850-6_2.
short: 'S. Abshoff, M. Benter, M. Malatyali, F. Meyer auf der Heide, in: Proceedings
of the 17th International Conference on Principles of Distributed Systems (OPODIS),
2013, pp. 11–22.'
date_created: 2017-10-17T12:42:31Z
date_updated: 2022-01-06T07:01:36Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-319-03850-6_2
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:47:31Z
date_updated: 2018-03-15T10:47:31Z
file_id: '1305'
file_name: 507-on-two-party-communication-through-dynamic-networks_01.pdf
file_size: 181398
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:47:31Z
has_accepted_license: '1'
page: 11-22
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 17th International Conference on Principles of Distributed
Systems (OPODIS)
series_title: LNCS
status: public
title: On Two-Party Communication Through Dynamic Networks
type: conference
user_id: '15504'
year: '2013'
...
---
_id: '514'
abstract:
- lang: eng
text: Diese Arbeit besch{\"a}ftigt sich mit dem Facility Location Problem. Dies
ist ein Optimierungsproblem, bei dem festgelegt werden muss an welchen Positionen
Ressourcen zur Verf{\"u}gung gestellt werden, so dass diese von Nutzern gut erreicht
werden k{\"o}nnen. Es sollen dabei Kosten minimiert werden, die zum einen durch
Bereitstellung von Ressourcen und zum anderen durch Verbindungskosten zwischen
Nutzern und Ressourcen entstehen. Die Schwierigkeit des Problems liegt darin,
dass man einerseits m{\"o}glichst wenige Ressourcen zur Verf{\"u}gung stellen
m{\"o}chte, andererseits daf{\"u}r sorgen muss, dass sich Nutzer nicht all zu
weit weg von Ressourcen befinden. Dies w{\"u}rde n{\"a}mlich hohe Verbindungskosten
nach sich ziehen. Das Facility Location Problem wurde bereits sehr intensiv in
vielen unterschiedlichen Varianten untersucht. In dieser Arbeit werden drei Varianten
des Problems modelliert und neue Algorithmen f{\"u}r sie entwickelt und bez{\"u}glich
ihres Approximationsfaktors und ihrer Laufzeit analysiert. Jede dieser drei untersuchten
Varianten hat einen besonderen Schwerpunkt. Bei der ersten Varianten handelt es
sich um ein Online Problem, da hier die Eingabe nicht von Anfang an bekannt ist,
sondern Schritt f{\"u}r Schritt enth{\"u}llt wird. Die Schwierigkeit hierbei besteht
darin unwiderrufliche Entscheidungen treffen zu m{\"u}ssen ohne dabei die Zukunft
zu kennen und trotzdem eine zu jeder Zeit gute L{\"o}sung angeben zu k{\"o}nnen.
Der Schwerpunkt der zweiten Variante liegt auf Lokalit{\"a}t, die z.B. in Sensornetzwerken
von großer Bedeutung ist. Hier soll eine L{\"o}sung verteilt und nur mit Hilfe
von lokalen Information berechnet werden. Schließlich besch{\"a}ftigt sich die
dritte Variante mit einer verteilten Berechnung, bei welcher nur eine stark beschr{\"a}nkte
Datenmenge verschickt werden darf und dabei trotzdem ein sehr guter Approximationsfaktor
erreicht werden muss. Die bei der Analyse der Approximationsfaktoren bzw. der
Kompetitivit{\"a}t verwendeten Techniken basieren zum großen Teil auf Absch{\"a}tzung
der primalen L{\"o}sung mit Hilfe einer L{\"o}sung des zugeh{\"o}rigen dualen
Problems. F{\"u}r die Modellierung von Lokalit{\"a}t wird das weitverbreitete
LOCAL Modell verwendet. In diesem Modell werden f{\"u}r die Algorithmen subpolynomielle
obere Laufzeitschranken gezeigt.
author:
- first_name: Peter
full_name: Pietrzyk, Peter
last_name: Pietrzyk
citation:
ama: Pietrzyk P. Local and Online Algorithms for Facility Location. Universität
Paderborn; 2013.
apa: Pietrzyk, P. (2013). Local and Online Algorithms for Facility Location.
Universität Paderborn.
bibtex: '@book{Pietrzyk_2013, title={Local and Online Algorithms for Facility Location},
publisher={Universität Paderborn}, author={Pietrzyk, Peter}, year={2013} }'
chicago: Pietrzyk, Peter. Local and Online Algorithms for Facility Location.
Universität Paderborn, 2013.
ieee: P. Pietrzyk, Local and Online Algorithms for Facility Location. Universität
Paderborn, 2013.
mla: Pietrzyk, Peter. Local and Online Algorithms for Facility Location.
Universität Paderborn, 2013.
short: P. Pietrzyk, Local and Online Algorithms for Facility Location, Universität
Paderborn, 2013.
date_created: 2017-10-17T12:42:32Z
date_updated: 2022-01-06T07:01:38Z
ddc:
- '040'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:44:13Z
date_updated: 2018-03-15T10:44:13Z
file_id: '1302'
file_name: 514-DissertationPietrzyk.pdf
file_size: 790821
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:44:13Z
has_accepted_license: '1'
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: Local and Online Algorithms for Facility Location
type: dissertation
user_id: '477'
year: '2013'
...
---
_id: '524'
abstract:
- lang: eng
text: 'We study the complexity theory for the local distributed setting introduced
by Korman, Peleg and Fraigniaud. They have defined three complexity classes LD
(Local Decision), NLD (Nondeterministic Local Decision) and NLD^#n. The class
LD consists of all languages which can be decided with a constant number of communication
rounds. The class NLD consists of all languages which can be verified by a nondeterministic
algorithm with a constant number of communication rounds. In order to define the
nondeterministic classes, they have transferred the notation of nondeterminism
into the distributed setting by the use of certificates and verifiers. The class
NLD^#n consists of all languages which can be verified by a nondeterministic algorithm
where each node has access to an oracle for the number of nodes. They have shown
the hierarchy LD subset NLD subset NLD^#n. Our main contributions are strict hierarchies
within the classes defined by Korman, Peleg and Fraigniaud. We define additional
complexity classes: the class LD(t) consists of all languages which can be decided
with at most t communication rounds. The class NLD-O(f) consists of all languages
which can be verified by a local verifier such that the size of the certificates
that are needed to verify the language are bounded by a function from O(f). Our
main results are refined strict hierarchies within these nondeterministic classes.'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Kamil
full_name: Swirkot, Kamil
last_name: Swirkot
citation:
ama: Meyer auf der Heide F, Swirkot K. Hierarchies in Local Distributed Decision.
2013.
apa: Meyer auf der Heide, F., & Swirkot, K. (2013). Hierarchies in Local Distributed
Decision. arXiv.
bibtex: '@article{Meyer auf der Heide_Swirkot_2013, title={Hierarchies in Local
Distributed Decision}, publisher={arXiv}, author={Meyer auf der Heide, Friedhelm
and Swirkot, Kamil}, year={2013} }'
chicago: Meyer auf der Heide, Friedhelm, and Kamil Swirkot. “Hierarchies in Local
Distributed Decision.” arXiv, 2013.
ieee: F. Meyer auf der Heide and K. Swirkot, “Hierarchies in Local Distributed Decision.”
arXiv, 2013.
mla: Meyer auf der Heide, Friedhelm, and Kamil Swirkot. Hierarchies in Local
Distributed Decision. arXiv, 2013.
short: F. Meyer auf der Heide, K. Swirkot, (2013).
date_created: 2017-10-17T12:42:34Z
date_updated: 2022-01-06T07:01:48Z
ddc:
- '040'
department:
- _id: '63'
external_id:
arxiv:
- '1311.7229'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:37:07Z
date_updated: 2018-03-15T10:37:07Z
file_id: '1296'
file_name: 524-paper_01.pdf
file_size: 534906
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:37:07Z
has_accepted_license: '1'
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: arXiv
status: public
title: Hierarchies in Local Distributed Decision
type: preprint
user_id: '15415'
year: '2013'
...
---
_id: '558'
citation:
ama: Flocchini P, Gao J, Kranakis E, Meyer auf der Heide F, eds. Algorithms for
Sensor Systems - 9th International Symposium on Algorithms and Experiments for
Sensor Systems, Wireless Networks and Distributed Robotics. Vol 8243. Springer;
2013. doi:10.1007/978-3-642-45346-5
apa: 'Flocchini, P., Gao, J., Kranakis, E., & Meyer auf der Heide, F. (Eds.).
(2013). Algorithms for Sensor Systems - 9th International Symposium on Algorithms
and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics
(Vol. 8243). Presented at the ALGOSENSORS 2013, Sophia Antipolis, France: Springer.
https://doi.org/10.1007/978-3-642-45346-5'
bibtex: '@book{Flocchini_Gao_Kranakis_Meyer auf der Heide_2013, series={LNCS}, title={Algorithms
for Sensor Systems - 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics}, volume={8243},
DOI={10.1007/978-3-642-45346-5},
publisher={Springer}, year={2013}, collection={LNCS} }'
chicago: Flocchini, Paola, Jie Gao, Evangelos Kranakis, and Friedhelm Meyer auf
der Heide, eds. Algorithms for Sensor Systems - 9th International Symposium
on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed
Robotics. Vol. 8243. LNCS. Springer, 2013. https://doi.org/10.1007/978-3-642-45346-5.
ieee: P. Flocchini, J. Gao, E. Kranakis, and F. Meyer auf der Heide, Eds., Algorithms
for Sensor Systems - 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics, vol. 8243.
Springer, 2013.
mla: Flocchini, Paola, et al., editors. Algorithms for Sensor Systems - 9th International
Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks
and Distributed Robotics. Vol. 8243, Springer, 2013, doi:10.1007/978-3-642-45346-5.
short: P. Flocchini, J. Gao, E. Kranakis, F. Meyer auf der Heide, eds., Algorithms
for Sensor Systems - 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics, Springer, 2013.
conference:
end_date: 2013-09-06
location: Sophia Antipolis, France
name: ALGOSENSORS 2013
start_date: 2013-09-05
date_created: 2017-10-17T12:42:41Z
date_updated: 2022-01-06T07:02:02Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-642-45346-5
editor:
- first_name: Paola
full_name: Flocchini, Paola
last_name: Flocchini
- first_name: Jie
full_name: Gao, Jie
last_name: Gao
- first_name: Evangelos
full_name: Kranakis, Evangelos
last_name: Kranakis
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T16:29:07Z
date_updated: 2018-11-02T16:29:07Z
file_id: '5327'
file_name: 2014_Book_AlgorithmsForSensorSystems-1.pdf
file_size: 9186107
relation: main_file
success: 1
file_date_updated: 2018-11-02T16:29:07Z
has_accepted_license: '1'
intvolume: ' 8243'
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: Springer
series_title: LNCS
status: public
title: Algorithms for Sensor Systems - 9th International Symposium on Algorithms and
Experiments for Sensor Systems, Wireless Networks and Distributed Robotics
type: conference_editor
user_id: '477'
volume: 8243
year: '2013'
...
---
_id: '562'
abstract:
- lang: eng
text: In Distributed Cloud Computing, applications are deployed across many data
centres at topologically diverse locations to improved network-related quality
of service (QoS). As we focus on interactive applications, we minimize the latency
between users and an application by allocating Cloud resources nearby the customers.
Allocating resources at all locations will result in the best latency but also
in the highest expenses. So we need to find an optimal subset of locations which
reduces the latency but also the expenses – the facility location problem (FLP).
In addition, we consider resource capacity restrictions, as a resource can only
serve a limited amount of users. An FLP can be globally solved. Additionally,
we propose a local, distributed heuristic. This heuristic is running within the
network and does not depend on a global component. No distributed, local approximations
for the capacitated FLP have been proposed so far due to the complexity of the
problem. We compared the heuristic with an optimal solution obtained from a mixed
integer program for different network topologies. We investigated the influence
of different parameters like overall resource utilization or different latency
weights.
author:
- first_name: Matthias
full_name: Keller, Matthias
last_name: Keller
- first_name: Stefan
full_name: Pawlik, Stefan
last_name: Pawlik
- first_name: Peter
full_name: Pietrzyk, Peter
last_name: Pietrzyk
- first_name: Holger
full_name: Karl, Holger
id: '126'
last_name: Karl
citation:
ama: 'Keller M, Pawlik S, Pietrzyk P, Karl H. A Local Heuristic for Latency-Optimized
Distributed Cloud Deployment. In: Proceedings of the 6th International Conference
on Utility and Cloud Computing (UCC) Workshop on Distributed Cloud Computing.
; 2013:429-434. doi:10.1109/UCC.2013.85'
apa: Keller, M., Pawlik, S., Pietrzyk, P., & Karl, H. (2013). A Local Heuristic
for Latency-Optimized Distributed Cloud Deployment. In Proceedings of the 6th
International Conference on Utility and Cloud Computing (UCC) workshop on Distributed
cloud computing (pp. 429–434). https://doi.org/10.1109/UCC.2013.85
bibtex: '@inproceedings{Keller_Pawlik_Pietrzyk_Karl_2013, title={A Local Heuristic
for Latency-Optimized Distributed Cloud Deployment}, DOI={10.1109/UCC.2013.85},
booktitle={Proceedings of the 6th International Conference on Utility and Cloud
Computing (UCC) workshop on Distributed cloud computing}, author={Keller, Matthias
and Pawlik, Stefan and Pietrzyk, Peter and Karl, Holger}, year={2013}, pages={429–434}
}'
chicago: Keller, Matthias, Stefan Pawlik, Peter Pietrzyk, and Holger Karl. “A Local
Heuristic for Latency-Optimized Distributed Cloud Deployment.” In Proceedings
of the 6th International Conference on Utility and Cloud Computing (UCC) Workshop
on Distributed Cloud Computing, 429–34, 2013. https://doi.org/10.1109/UCC.2013.85.
ieee: M. Keller, S. Pawlik, P. Pietrzyk, and H. Karl, “A Local Heuristic for Latency-Optimized
Distributed Cloud Deployment,” in Proceedings of the 6th International Conference
on Utility and Cloud Computing (UCC) workshop on Distributed cloud computing,
2013, pp. 429–434.
mla: Keller, Matthias, et al. “A Local Heuristic for Latency-Optimized Distributed
Cloud Deployment.” Proceedings of the 6th International Conference on Utility
and Cloud Computing (UCC) Workshop on Distributed Cloud Computing, 2013, pp.
429–34, doi:10.1109/UCC.2013.85.
short: 'M. Keller, S. Pawlik, P. Pietrzyk, H. Karl, in: Proceedings of the 6th International
Conference on Utility and Cloud Computing (UCC) Workshop on Distributed Cloud
Computing, 2013, pp. 429–434.'
date_created: 2017-10-17T12:42:41Z
date_updated: 2022-01-06T07:02:11Z
ddc:
- '040'
department:
- _id: '75'
- _id: '63'
doi: 10.1109/UCC.2013.85
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:25:45Z
date_updated: 2018-03-15T10:25:45Z
file_id: '1279'
file_name: 562-dcc13_paper.pdf
file_size: 347873
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:25:45Z
has_accepted_license: '1'
language:
- iso: eng
page: 429-434
project:
- _id: '1'
name: SFB 901
- _id: '6'
name: SFB 901 - Subprojekt A2
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 6th International Conference on Utility and Cloud
Computing (UCC) workshop on Distributed cloud computing
status: public
title: A Local Heuristic for Latency-Optimized Distributed Cloud Deployment
type: conference
user_id: '477'
year: '2013'
...
---
_id: '563'
abstract:
- lang: eng
text: Dominating set based virtual backbones are used for rou-ting in wireless ad-hoc
networks. Such backbones receive and transmit messages from/to every node in the
network. Existing distributed algorithms only consider undirected graphs, which
model symmetric networks with uniform transmission ranges. We are particularly
interested in the well-established disk graphs, which model asymmetric networks
with non-uniform transmission ranges. The corresponding graph theoretic problem
seeks a strongly connected dominating-absorbent set of minimum cardinality in
a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent
set if the subgraph induced by these nodes is strongly connected and each node
in the graph is either in the set or has both an in-neighbor and an out-neighbor
in it. We introduce the first distributed algorithm for this problem in disk graphs.
The algorithm gives an O(k^4) -approximation ratio and has a runtime bound of
O(Diam) where Diam is the diameter of the graph and k denotes the transmission
ratio r_{max}/r_{min} with r_{max} and r_{min} being the maximum and minimum transmission
range, respectively. Moreover, we apply our algorithm on the subgraph of disk
graphs consisting of only bidirectional edges. Our algorithm gives an O(ln k)
-approximation and a runtime bound of O(k^8 log^∗ n) , which, for bounded k ,
is an optimal approximation for the problem, following Lenzen and Wattenhofer’s
Ω(log^∗ n) runtime lower bound for distributed constant approximation in disk
graphs.
author:
- first_name: Christine
full_name: Markarian, Christine
id: '37612'
last_name: Markarian
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Michael
full_name: Schubert, Michael
last_name: Schubert
citation:
ama: 'Markarian C, Meyer auf der Heide F, Schubert M. A Distributed Approximation
Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless
Ad-Hoc Networks. In: Proceedings of the 9th International Symposium on Algorithms
and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics
(ALGOSENSORS). LNCS. ; 2013:217-227. doi:10.1007/978-3-642-45346-5_16'
apa: Markarian, C., Meyer auf der Heide, F., & Schubert, M. (2013). A Distributed
Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric
Wireless Ad-Hoc Networks. In Proceedings of the 9th International Symposium
on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed
Robotics (ALGOSENSORS) (pp. 217–227). https://doi.org/10.1007/978-3-642-45346-5_16
bibtex: '@inproceedings{Markarian_Meyer auf der Heide_Schubert_2013, series={LNCS},
title={A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent
Sets in Asymmetric Wireless Ad-Hoc Networks}, DOI={10.1007/978-3-642-45346-5_16},
booktitle={Proceedings of the 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)},
author={Markarian, Christine and Meyer auf der Heide, Friedhelm and Schubert,
Michael}, year={2013}, pages={217–227}, collection={LNCS} }'
chicago: Markarian, Christine, Friedhelm Meyer auf der Heide, and Michael Schubert.
“A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent
Sets in Asymmetric Wireless Ad-Hoc Networks.” In Proceedings of the 9th International
Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks
and Distributed Robotics (ALGOSENSORS), 217–27. LNCS, 2013. https://doi.org/10.1007/978-3-642-45346-5_16.
ieee: C. Markarian, F. Meyer auf der Heide, and M. Schubert, “A Distributed Approximation
Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless
Ad-Hoc Networks,” in Proceedings of the 9th International Symposium on Algorithms
and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics
(ALGOSENSORS), 2013, pp. 217–227.
mla: Markarian, Christine, et al. “A Distributed Approximation Algorithm for Strongly
Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks.” Proceedings
of the 9th International Symposium on Algorithms and Experiments for Sensor Systems,
Wireless Networks and Distributed Robotics (ALGOSENSORS), 2013, pp. 217–27,
doi:10.1007/978-3-642-45346-5_16.
short: 'C. Markarian, F. Meyer auf der Heide, M. Schubert, in: Proceedings of the
9th International Symposium on Algorithms and Experiments for Sensor Systems,
Wireless Networks and Distributed Robotics (ALGOSENSORS), 2013, pp. 217–227.'
date_created: 2017-10-17T12:42:42Z
date_updated: 2022-01-06T07:02:13Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-45346-5_16
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:25:15Z
date_updated: 2018-03-15T10:25:15Z
file_id: '1278'
file_name: 563-978-3-642-45346-5_16.pdf
file_size: 348191
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:25:15Z
has_accepted_license: '1'
page: 217-227
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 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)
series_title: LNCS
status: public
title: A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent
Sets in Asymmetric Wireless Ad-Hoc Networks
type: conference
user_id: '477'
year: '2013'
...
---
_id: '16393'
abstract:
- lang: eng
text: Many 3D scenes (e.g. generated from CAD data) are composed of a multitude
of objects that are nested in each other. A showroom, for instance, may contain
multiple cars and every car has a gearbox with many gearwheels located inside.
Because the objects occlude each other, only few are visible from outside. We
present a new technique, Spherical Visibility Sampling (SVS), for real-time 3D
rendering of such -- possibly highly complex -- scenes. SVS exploits the occlusion
and annotates hierarchically structured objects with directional visibility information
in a preprocessing step. For different directions, the directional visibility
encodes which objects of a scene's region are visible from the outside of the
regions' enclosing bounding sphere. Since there is no need to store a separate
view space subdivision as in most techniques based on preprocessed visibility,
a small memory footprint is achieved. Using the directional visibility information
for an interactive walkthrough, the potentially visible objects can be retrieved
very efficiently without the need for further visibility tests. Our evaluation
shows that using SVS allows to preprocess complex 3D scenes fast and to visualize
them in real time (e.g. a Power Plant model and five animated Boeing 777 models
with billions of triangles). Because SVS does not require hardware support for
occlusion culling during rendering, it is even applicable for rendering large
scenes on mobile devices.
author:
- first_name: Benjamin
full_name: Eikel, Benjamin
last_name: Eikel
- first_name: Claudius
full_name: Jähn, Claudius
last_name: Jähn
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Eikel B, Jähn C, Fischer M, Meyer auf der Heide F. Spherical Visibility Sampling.
In: Computer Graphics Forum. Vol 32. Proceedings of the 24th Eurographics
Symposium on Rendering. ; 2013:49-58. doi:10.1111/cgf.12150'
apa: Eikel, B., Jähn, C., Fischer, M., & Meyer auf der Heide, F. (2013). Spherical
Visibility Sampling. In Computer Graphics Forum (Vol. 32, pp. 49–58). https://doi.org/10.1111/cgf.12150
bibtex: '@inproceedings{Eikel_Jähn_Fischer_Meyer auf der Heide_2013, series={Proceedings
of the 24th Eurographics Symposium on Rendering}, title={Spherical Visibility
Sampling}, volume={32}, DOI={10.1111/cgf.12150},
number={4}, booktitle={Computer Graphics Forum}, author={Eikel, Benjamin and Jähn,
Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm}, year={2013},
pages={49–58}, collection={Proceedings of the 24th Eurographics Symposium on Rendering}
}'
chicago: Eikel, Benjamin, Claudius Jähn, Matthias Fischer, and Friedhelm Meyer auf
der Heide. “Spherical Visibility Sampling.” In Computer Graphics Forum,
32:49–58. Proceedings of the 24th Eurographics Symposium on Rendering, 2013. https://doi.org/10.1111/cgf.12150.
ieee: B. Eikel, C. Jähn, M. Fischer, and F. Meyer auf der Heide, “Spherical Visibility
Sampling,” in Computer Graphics Forum, 2013, vol. 32, no. 4, pp. 49–58.
mla: Eikel, Benjamin, et al. “Spherical Visibility Sampling.” Computer Graphics
Forum, vol. 32, no. 4, 2013, pp. 49–58, doi:10.1111/cgf.12150.
short: 'B. Eikel, C. Jähn, M. Fischer, F. Meyer auf der Heide, in: Computer Graphics
Forum, 2013, pp. 49–58.'
date_created: 2020-04-03T07:48:48Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1111/cgf.12150
intvolume: ' 32'
issue: '4'
language:
- iso: eng
page: 49-58
publication: Computer Graphics Forum
publication_identifier:
issn:
- 0167-7055
publication_status: published
series_title: Proceedings of the 24th Eurographics Symposium on Rendering
status: public
title: Spherical Visibility Sampling
type: conference
user_id: '15415'
volume: 32
year: '2013'
...
---
_id: '16406'
abstract:
- lang: eng
text: "In order to evaluate the efficiency of algorithms for real-time 3D rendering,
different properties like rendering time, occluded triangles, or image quality,
need to be investigated. Since these properties depend on the position of the
camera, usually some camera path is chosen, along which the measurements are performed.
As those measurements cover only a small part of the scene, this approach hardly
allows drawing conclusions regarding the algorithm's properties at arbitrary positions
in the scene. The presented method allows the systematic and position-independent
evaluation of rendering algorithms. It uses an adaptive sampling approach to approximate
the distribution of a property (like rendering time) for all positions in the
scene. This approximation can be visualized to produce an intuitive impression
of the algorithm's behavior or be statistically analyzed for objectively rating
and comparing algorithms. We demonstrate our method by evaluating performance
aspects of a known occlusion culling algorithm.\r\n"
author:
- first_name: Claudius
full_name: Jähn, Claudius
last_name: Jähn
- first_name: Benjamin
full_name: Eikel, Benjamin
last_name: Eikel
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Ralf
full_name: Petring, Ralf
last_name: Petring
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Jähn C, Eikel B, Fischer M, Petring R, Meyer auf der Heide F. Evaluation of
Rendering Algorithms Using Position-Dependent Scene Properties. In: Advances
in Visual Computing. Berlin, Heidelberg; 2013. doi:10.1007/978-3-642-41914-0_12'
apa: Jähn, C., Eikel, B., Fischer, M., Petring, R., & Meyer auf der Heide, F.
(2013). Evaluation of Rendering Algorithms Using Position-Dependent Scene Properties.
In Advances in Visual Computing. Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41914-0_12
bibtex: '@inbook{Jähn_Eikel_Fischer_Petring_Meyer auf der Heide_2013, place={Berlin,
Heidelberg}, title={Evaluation of Rendering Algorithms Using Position-Dependent
Scene Properties}, DOI={10.1007/978-3-642-41914-0_12},
booktitle={Advances in Visual Computing}, author={Jähn, Claudius and Eikel, Benjamin
and Fischer, Matthias and Petring, Ralf and Meyer auf der Heide, Friedhelm}, year={2013}
}'
chicago: Jähn, Claudius, Benjamin Eikel, Matthias Fischer, Ralf Petring, and Friedhelm
Meyer auf der Heide. “Evaluation of Rendering Algorithms Using Position-Dependent
Scene Properties.” In Advances in Visual Computing. Berlin, Heidelberg,
2013. https://doi.org/10.1007/978-3-642-41914-0_12.
ieee: C. Jähn, B. Eikel, M. Fischer, R. Petring, and F. Meyer auf der Heide, “Evaluation
of Rendering Algorithms Using Position-Dependent Scene Properties,” in Advances
in Visual Computing, Berlin, Heidelberg, 2013.
mla: Jähn, Claudius, et al. “Evaluation of Rendering Algorithms Using Position-Dependent
Scene Properties.” Advances in Visual Computing, 2013, doi:10.1007/978-3-642-41914-0_12.
short: 'C. Jähn, B. Eikel, M. Fischer, R. Petring, F. Meyer auf der Heide, in: Advances
in Visual Computing, Berlin, Heidelberg, 2013.'
date_created: 2020-04-06T07:21:55Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-41914-0_12
language:
- iso: eng
place: Berlin, Heidelberg
publication: Advances in Visual Computing
publication_identifier:
isbn:
- '9783642419133'
- '9783642419140'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Evaluation of Rendering Algorithms Using Position-Dependent Scene Properties
type: book_chapter
user_id: '15415'
year: '2013'
...
---
_id: '16407'
abstract:
- lang: eng
text: "Many virtual 3D scenes, especially those that are large, are not structured
evenly. For such heterogeneous data, there is no single algorithm that is able
to render every scene type at each position fast and with the same high image
quality. For a small set of scenes, this situation can be improved if different
rendering algorithms are manually assigned to particular parts of the scene by
an experienced user. We introduce the Multi-Algorithm-Rendering method. It automatically
deploys different rendering algorithms simultaneously for a broad range of scene
types. The method divides the scene into subregions and measures the behavior
of different algorithms for each region in a preprocessing step. During runtime,
this data is utilized to compute an estimate for the quality and running time
of the available rendering algorithms from the observer's point of view. By solving
an optimizing problem, the image quality can be optimized by an assignment of
algorithms to regions while keeping the frame rate almost constant.\r\n"
author:
- first_name: Ralf
full_name: Petring, Ralf
last_name: Petring
- first_name: Benjamin
full_name: Eikel, Benjamin
last_name: Eikel
- first_name: Claudius
full_name: Jähn, Claudius
last_name: Jähn
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Petring R, Eikel B, Jähn C, Fischer M, Meyer auf der Heide F. Real-Time 3D
Rendering of Heterogeneous Scenes. In: Advances in Visual Computing. Berlin,
Heidelberg; 2013. doi:10.1007/978-3-642-41914-0_44'
apa: Petring, R., Eikel, B., Jähn, C., Fischer, M., & Meyer auf der Heide, F.
(2013). Real-Time 3D Rendering of Heterogeneous Scenes. In Advances in Visual
Computing. Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41914-0_44
bibtex: '@inbook{Petring_Eikel_Jähn_Fischer_Meyer auf der Heide_2013, place={Berlin,
Heidelberg}, title={Real-Time 3D Rendering of Heterogeneous Scenes}, DOI={10.1007/978-3-642-41914-0_44},
booktitle={Advances in Visual Computing}, author={Petring, Ralf and Eikel, Benjamin
and Jähn, Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm},
year={2013} }'
chicago: Petring, Ralf, Benjamin Eikel, Claudius Jähn, Matthias Fischer, and Friedhelm
Meyer auf der Heide. “Real-Time 3D Rendering of Heterogeneous Scenes.” In Advances
in Visual Computing. Berlin, Heidelberg, 2013. https://doi.org/10.1007/978-3-642-41914-0_44.
ieee: R. Petring, B. Eikel, C. Jähn, M. Fischer, and F. Meyer auf der Heide, “Real-Time
3D Rendering of Heterogeneous Scenes,” in Advances in Visual Computing,
Berlin, Heidelberg, 2013.
mla: Petring, Ralf, et al. “Real-Time 3D Rendering of Heterogeneous Scenes.” Advances
in Visual Computing, 2013, doi:10.1007/978-3-642-41914-0_44.
short: 'R. Petring, B. Eikel, C. Jähn, M. Fischer, F. Meyer auf der Heide, in: Advances
in Visual Computing, Berlin, Heidelberg, 2013.'
date_created: 2020-04-06T07:38:52Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-41914-0_44
language:
- iso: eng
place: Berlin, Heidelberg
publication: Advances in Visual Computing
publication_identifier:
isbn:
- '9783642419133'
- '9783642419140'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Real-Time 3D Rendering of Heterogeneous Scenes
type: book_chapter
user_id: '15415'
year: '2013'
...
---
_id: '505'
abstract:
- lang: eng
text: In this paper we introduce “On-The-Fly Computing”, our vision of future IT
services that will be provided by assembling modular software components available
on world-wide markets. After suitable components have been found, they are automatically
integrated, configured and brought to execution in an On-The-Fly Compute Center.
We envision that these future compute centers will continue to leverage three
current trends in large scale computing which are an increasing amount of parallel
processing, a trend to use heterogeneous computing resources, and—in the light
of rising energy cost—energy-efficiency as a primary goal in the design and operation
of computing systems. In this paper, we point out three research challenges and
our current work in these areas.
author:
- first_name: Markus
full_name: Happe, Markus
last_name: Happe
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Christian
full_name: Plessl, Christian
id: '16153'
last_name: Plessl
orcid: 0000-0001-5728-9982
- first_name: Marco
full_name: Platzner, Marco
id: '398'
last_name: Platzner
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Happe M, Kling P, Plessl C, Platzner M, Meyer auf der Heide F. On-The-Fly
Computing: A Novel Paradigm for Individualized IT Services. In: Proceedings
of the 9th IEEE Workshop on Software Technology for Future Embedded and Ubiquitous
Systems (SEUS). IEEE; 2013. doi:10.1109/ISORC.2013.6913232'
apa: 'Happe, M., Kling, P., Plessl, C., Platzner, M., & Meyer auf der Heide,
F. (2013). On-The-Fly Computing: A Novel Paradigm for Individualized IT Services.
Proceedings of the 9th IEEE Workshop on Software Technology for Future Embedded
and Ubiquitous Systems (SEUS). https://doi.org/10.1109/ISORC.2013.6913232'
bibtex: '@inproceedings{Happe_Kling_Plessl_Platzner_Meyer auf der Heide_2013, title={On-The-Fly
Computing: A Novel Paradigm for Individualized IT Services}, DOI={10.1109/ISORC.2013.6913232},
booktitle={Proceedings of the 9th IEEE Workshop on Software Technology for Future
embedded and Ubiquitous Systems (SEUS)}, publisher={IEEE}, author={Happe, Markus
and Kling, Peter and Plessl, Christian and Platzner, Marco and Meyer auf der Heide,
Friedhelm}, year={2013} }'
chicago: 'Happe, Markus, Peter Kling, Christian Plessl, Marco Platzner, and Friedhelm
Meyer auf der Heide. “On-The-Fly Computing: A Novel Paradigm for Individualized
IT Services.” In Proceedings of the 9th IEEE Workshop on Software Technology
for Future Embedded and Ubiquitous Systems (SEUS). IEEE, 2013. https://doi.org/10.1109/ISORC.2013.6913232.'
ieee: 'M. Happe, P. Kling, C. Plessl, M. Platzner, and F. Meyer auf der Heide, “On-The-Fly
Computing: A Novel Paradigm for Individualized IT Services,” 2013, doi: 10.1109/ISORC.2013.6913232.'
mla: 'Happe, Markus, et al. “On-The-Fly Computing: A Novel Paradigm for Individualized
IT Services.” Proceedings of the 9th IEEE Workshop on Software Technology for
Future Embedded and Ubiquitous Systems (SEUS), IEEE, 2013, doi:10.1109/ISORC.2013.6913232.'
short: 'M. Happe, P. Kling, C. Plessl, M. Platzner, F. Meyer auf der Heide, in:
Proceedings of the 9th IEEE Workshop on Software Technology for Future Embedded
and Ubiquitous Systems (SEUS), IEEE, 2013.'
date_created: 2017-10-17T12:42:30Z
date_updated: 2023-09-26T13:38:20Z
ddc:
- '040'
department:
- _id: '63'
- _id: '27'
- _id: '518'
- _id: '78'
doi: 10.1109/ISORC.2013.6913232
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T13:38:56Z
date_updated: 2018-03-15T13:38:56Z
file_id: '1308'
file_name: 505-Plessl13_seus.pdf
file_size: 1040834
relation: main_file
success: 1
file_date_updated: 2018-03-15T13:38:56Z
has_accepted_license: '1'
language:
- iso: eng
project:
- _id: '1'
grant_number: '160364472'
name: SFB 901
- _id: '14'
grant_number: '160364472'
name: SFB 901 - Subprojekt C2
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 9th IEEE Workshop on Software Technology for Future
embedded and Ubiquitous Systems (SEUS)
publisher: IEEE
quality_controlled: '1'
status: public
title: 'On-The-Fly Computing: A Novel Paradigm for Individualized IT Services'
type: conference
user_id: '15278'
year: '2013'
...
---
_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'
...