---
_id: '18976'
abstract:
- lang: eng
text: "Web computing is a variant of parallel computing where the idle times of
PCs\r\ndonated by worldwide distributed users are employed to execute parallel\r\nprograms.
In this thesis we consider a web computing variant with two\r\nimportant properties:
First, we support the execution of coupled, massively\r\nparallel algorithms (rather
than distributed data processing). And second,\r\nwe organize the system in peer-to-peer
fashion.\r\n\r\nWe present the Paderborn University BSP-based Web Computing (PUB-Web)
library,\r\nwhich supports the execution of parallel programs in the bulk-synchronous
style\r\n(BSP) in such a web computing setting. In this thesis, we focus on important\r\ntechnical
and algorithmic aspects, in particular: In order to schedule\r\nprocesses with
respect to the currently available computing power, which\r\ncontinually changes
in an unpredictable fashion, we need intelligent load\r\nbalancing algorithms
and -- as a basic precondition -- the technical ability\r\nto migrate threads
at runtime.\r\n\r\nTo achieve the latter in a way suitable for production use,
compatible with\r\nrecent Java versions, available for all important platforms,
and easy-to-use\r\nfor developers, we develop the PadMig thread migration and
checkpointing\r\nlibrary.\r\n\r\nIn order to tackle the distributed load balancing
problem, we present an\r\nalgorithm based on Distributed Heterogeneous Hash-Tables.
In order to judge\r\nthe quality of the schedules produced, we perform extensive
experiments to\r\ncompare several variants of the DHHT-based load balancer with
the well-\r\nestablished Work Stealing algorithm, using realistic input data obtained
by\r\nprofiling the utilization of several hundred PCs for a period of several\r\nmonths.\r\n\r\nBeside
the available computing power, we finally also consider the network\r\nbandwidth
as a secondary criterion for load balancing. For this purpose, we\r\ncluster the
PUB-Web network according to bandwidth, employing a novel,\r\nfault-tolerant,
adaptive, and scaling distributed clustering algorithm called\r\nDiDiC. In order
to judge the quality of the clusterings produces by DiDiC,\r\nwe experimentally
compare it to the well-established MCL algorithm using a\r\nsimulator."
author:
- first_name: Joachim
full_name: Gehweiler, Joachim
last_name: Gehweiler
citation:
ama: Gehweiler J. Peer-to-Peer Based Parallel Web Computing. Vol 298. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn; 2011.
apa: Gehweiler, J. (2011). Peer-to-Peer Based Parallel Web Computing (Vol.
298). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn.
bibtex: '@book{Gehweiler_2011, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn}, title={Peer-to-Peer Based Parallel Web Computing}, volume={298}, publisher={Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn}, author={Gehweiler, Joachim}, year={2011},
collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn} }'
chicago: Gehweiler, Joachim. Peer-to-Peer Based Parallel Web Computing. Vol.
298. Verlagsschriftenreihe Des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2011.
ieee: J. Gehweiler, Peer-to-Peer Based Parallel Web Computing, vol. 298.
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2011.
mla: Gehweiler, Joachim. Peer-to-Peer Based Parallel Web Computing. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2011.
short: J. Gehweiler, Peer-to-Peer Based Parallel Web Computing, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2011.
date_created: 2020-09-04T07:46:32Z
date_updated: 2022-01-06T06:53:56Z
department:
- _id: '63'
- _id: '26'
intvolume: ' 298'
language:
- iso: eng
publication_identifier:
isbn:
- 978-3-942647-17-5
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
related_material:
link:
- relation: confirmation
url: http://digital.ub.uni-paderborn.de/ubpb/urn/urn:nbn:de:hbz:466:2-186
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
status: public
title: Peer-to-Peer Based Parallel Web Computing
type: dissertation
user_id: '5786'
volume: 298
year: '2011'
...
---
_id: '19026'
author:
- first_name: Patrick
full_name: Briest, Patrick
last_name: Briest
- first_name: Christoph
full_name: Raupach, Christoph
last_name: Raupach
citation:
ama: 'Briest P, Raupach C. The car sharing problem. In: Proceedings of the 23rd
ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’11. ;
2011. doi:10.1145/1989493.1989518'
apa: Briest, P., & Raupach, C. (2011). The car sharing problem. In Proceedings
of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA
’11. https://doi.org/10.1145/1989493.1989518
bibtex: '@inproceedings{Briest_Raupach_2011, title={The car sharing problem}, DOI={10.1145/1989493.1989518}, booktitle={Proceedings
of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA
’11}, author={Briest, Patrick and Raupach, Christoph}, year={2011} }'
chicago: Briest, Patrick, and Christoph Raupach. “The Car Sharing Problem.” In Proceedings
of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA
’11, 2011. https://doi.org/10.1145/1989493.1989518.
ieee: P. Briest and C. Raupach, “The car sharing problem,” in Proceedings of
the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA ’11,
2011.
mla: Briest, Patrick, and Christoph Raupach. “The Car Sharing Problem.” Proceedings
of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA
’11, 2011, doi:10.1145/1989493.1989518.
short: 'P. Briest, C. Raupach, in: Proceedings of the 23rd ACM Symposium on Parallelism
in Algorithms and Architectures - SPAA ’11, 2011.'
date_created: 2020-09-04T11:58:54Z
date_updated: 2022-01-06T06:53:57Z
department:
- _id: '63'
doi: 10.1145/1989493.1989518
language:
- iso: eng
publication: Proceedings of the 23rd ACM symposium on Parallelism in algorithms and
architectures - SPAA '11
publication_identifier:
isbn:
- '9781450307437'
publication_status: published
status: public
title: The car sharing problem
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '19040'
author:
- first_name: Sascha
full_name: Effert, Sascha
last_name: Effert
citation:
ama: Effert S. Verfahren Zur Redundanten Datenplatzierung in Skalierbaren Speichersystemen.
Universität Paderborn; 2011.
apa: Effert, S. (2011). Verfahren zur redundanten Datenplatzierung in skalierbaren
Speichersystemen. Universität Paderborn.
bibtex: '@book{Effert_2011, place={Universität Paderborn}, title={Verfahren zur
redundanten Datenplatzierung in skalierbaren Speichersystemen}, author={Effert,
Sascha}, year={2011} }'
chicago: Effert, Sascha. Verfahren Zur Redundanten Datenplatzierung in Skalierbaren
Speichersystemen. Universität Paderborn, 2011.
ieee: S. Effert, Verfahren zur redundanten Datenplatzierung in skalierbaren Speichersystemen.
Universität Paderborn, 2011.
mla: Effert, Sascha. Verfahren Zur Redundanten Datenplatzierung in Skalierbaren
Speichersystemen. 2011.
short: S. Effert, Verfahren Zur Redundanten Datenplatzierung in Skalierbaren Speichersystemen,
Universität Paderborn, 2011.
date_created: 2020-09-04T13:31:29Z
date_updated: 2022-01-06T06:53:57Z
department:
- _id: '63'
language:
- iso: eng
place: Universität Paderborn
related_material:
link:
- relation: confirmation
url: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-385
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Verfahren zur redundanten Datenplatzierung in skalierbaren Speichersystemen
type: dissertation
user_id: '15415'
year: '2011'
...
---
_id: '23739'
abstract:
- lang: eng
text: "This paper deals with the design of efficiently computable incentive-compatible
mechanisms for combinatorial optimization problems with single-minded agents each
possibly having multiple private parameters. We focus on approximation algorithms
for NP-hard mechanism design problems. These algorithms need to satisfy certain
monotonicity properties to ensure truthfulness. Since most of the known approximation
techniques do not fulfill these properties, we study alternative techniques. Our
first contribution is a quite general method to transform a pseudopolynomial algorithm
into a monotone fully polynomial time approximation scheme (FPTAS). This can be
applied to various problems like, e.g., knapsack, constrained shortest path, or
job scheduling with deadlines. For example, the monotone FPTAS for the knapsack
problem gives a very efficient, truthful mechanism for single-minded multiunit
auctions. The best previous result for such auctions was a 2-appro-xi-ma-tion.
In addition, we present a monotone PTAS for the generalized assignment problem
with any constant number of private parameters per agent. The most efficient way
to solve packing integer programs (PIPs) is linear programming–based randomized
rounding, which also is in general not monotone. We show that primal-dual greedy
algorithms achieve almost the same approximation ratios for PIPs as randomized
rounding. The advantage is that these algorithms are inherently monotone. This
way, we can significantly improve the approximation ratios of truthful mechanisms
for various fundamental mechanism design problems like single-minded combinatorial
auctions (CAs), unsplittable flow routing, and multicast routing. Our primal-dual
approximation algorithms can also be used for the winner determination in CAs
with general bidders specifying their bids through an oracle.\r\n"
author:
- first_name: Patrick
full_name: Briest, Patrick
last_name: Briest
- first_name: Piotr
full_name: Krysta, Piotr
last_name: Krysta
- first_name: Berthold
full_name: Vöcking, Berthold
last_name: Vöcking
citation:
ama: Briest P, Krysta P, Vöcking B. Approximation Techniques for Utilitarian Mechanism
Design. SIAM Journal on Computing. 2011:1587-1622. doi:10.1137/090772988
apa: Briest, P., Krysta, P., & Vöcking, B. (2011). Approximation Techniques
for Utilitarian Mechanism Design. SIAM Journal on Computing, 1587–1622.
https://doi.org/10.1137/090772988
bibtex: '@article{Briest_Krysta_Vöcking_2011, title={Approximation Techniques for
Utilitarian Mechanism Design}, DOI={10.1137/090772988},
journal={SIAM Journal on Computing}, author={Briest, Patrick and Krysta, Piotr
and Vöcking, Berthold}, year={2011}, pages={1587–1622} }'
chicago: Briest, Patrick, Piotr Krysta, and Berthold Vöcking. “Approximation Techniques
for Utilitarian Mechanism Design.” SIAM Journal on Computing, 2011, 1587–1622.
https://doi.org/10.1137/090772988.
ieee: P. Briest, P. Krysta, and B. Vöcking, “Approximation Techniques for Utilitarian
Mechanism Design,” SIAM Journal on Computing, pp. 1587–1622, 2011.
mla: Briest, Patrick, et al. “Approximation Techniques for Utilitarian Mechanism
Design.” SIAM Journal on Computing, 2011, pp. 1587–622, doi:10.1137/090772988.
short: P. Briest, P. Krysta, B. Vöcking, SIAM Journal on Computing (2011) 1587–1622.
date_created: 2021-09-03T10:41:04Z
date_updated: 2022-01-06T06:55:59Z
department:
- _id: '63'
doi: 10.1137/090772988
language:
- iso: eng
page: 1587-1622
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: Approximation Techniques for Utilitarian Mechanism Design
type: journal_article
user_id: '15415'
year: '2011'
...
---
_id: '23740'
abstract:
- lang: eng
text: "We investigate nonparametric multiproduct pricing problems, in which we want
to find revenue maximizing prices for products $\\mathcal{P}$ based on a set of
customer samples $\\mathcal{C}$. We mostly focus on the unit-demand case, in which
products constitute strict substitutes and each customer aims to purchase a single
product. In this setting a customer sample consists of a number of nonzero values
for different products and possibly an additional product ranking. Once prices
are fixed, each customer chooses to buy one of the products she can afford based
on some predefined selection rule. We distinguish between the min-buying, max-buying,
and rank-buying models. Some of our results also extend to single-minded pricing,
in which case products are strict complements and every customer seeks to buy
a single set of products, which she purchases if the sum of prices is below her
valuation for that set. For the min-buying model we show that the revenue maximization
problem is not approximable within factor $\\mathcal{O}(\\log^{\\varepsilon}|\\mathcal{C}|)$
for some constant $\\varepsilon>0$, unless $\\mathrm{NP}\\subseteq\\mathrm{DTIME}(n^{\\mathcal{O}(\\log\\log
n)})$, thereby almost closing the gap between the known algorithmic results and
previous lower bounds. We also prove inapproximability within $\\mathcal{O}(\\ell^{\\varepsilon})$,
$\\ell$ being an upper bound on the number of nonzero values per customer, and
$\\mathcal{O}(|\\mathcal{P}|^{\\varepsilon})$ under slightly stronger assumptions
and provide matching upper bounds. Surprisingly, these hardness results hold even
if a price ladder constraint, i.e., a predefined order on the prices of all products,
is given. Without the price ladder constraint we obtain similar hardness results
for the special case of uniform valuations, i.e., the case that every customer
has identical values for all the products she is interested in, assuming specific
hardness of the balanced bipartite independent set problem in constant degree
graphs or hardness of refuting random 3CNF formulas. Introducing a slightly more
general problem definition in which customers are given as an explicit probability
distribution, we obtain inapproximability within $\\mathcal{O}(|\\mathcal{P}|^{\\varepsilon})$
assuming $\\mathrm{NP}\\nsubseteq\\bigcap_{\\delta>0}\\mathrm{BPTIME}(2^{\\mathcal{O}(n^{\\delta})})$.
These results apply to single-minded pricing as well. For the max-buying model
a polynomial-time approximation scheme exists if a price ladder is given. We give
a matching lower bound by proving strong NP-hardness. Assuming limited product
supply, we analyze a generic local search algorithm and prove that it is 2-approximate.
Finally, we discuss implications for the rank-buying model.\r\n"
author:
- first_name: Patrick
full_name: Briest, Patrick
last_name: Briest
- first_name: Piotr
full_name: Krysta, Piotr
last_name: Krysta
citation:
ama: 'Briest P, Krysta P. Buying Cheap Is Expensive: Approximability of Combinatorial
Pricing Problems. SIAM Journal on Computing. 2011:1554-1586. doi:10.1137/090752353'
apa: 'Briest, P., & Krysta, P. (2011). Buying Cheap Is Expensive: Approximability
of Combinatorial Pricing Problems. SIAM Journal on Computing, 1554–1586.
https://doi.org/10.1137/090752353'
bibtex: '@article{Briest_Krysta_2011, title={Buying Cheap Is Expensive: Approximability
of Combinatorial Pricing Problems}, DOI={10.1137/090752353},
journal={SIAM Journal on Computing}, author={Briest, Patrick and Krysta, Piotr},
year={2011}, pages={1554–1586} }'
chicago: 'Briest, Patrick, and Piotr Krysta. “Buying Cheap Is Expensive: Approximability
of Combinatorial Pricing Problems.” SIAM Journal on Computing, 2011, 1554–86.
https://doi.org/10.1137/090752353.'
ieee: 'P. Briest and P. Krysta, “Buying Cheap Is Expensive: Approximability of Combinatorial
Pricing Problems,” SIAM Journal on Computing, pp. 1554–1586, 2011.'
mla: 'Briest, Patrick, and Piotr Krysta. “Buying Cheap Is Expensive: Approximability
of Combinatorial Pricing Problems.” SIAM Journal on Computing, 2011, pp.
1554–86, doi:10.1137/090752353.'
short: P. Briest, P. Krysta, SIAM Journal on Computing (2011) 1554–1586.
date_created: 2021-09-03T10:48:52Z
date_updated: 2022-01-06T06:55:59Z
department:
- _id: '63'
doi: 10.1137/090752353
language:
- iso: eng
page: 1554-1586
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: 'Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems'
type: journal_article
user_id: '15415'
year: '2011'
...
---
_id: '20709'
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Matthias
full_name: Fischer, Matthias
last_name: Fischer
- first_name: Martina
full_name: Hüllmann, Martina
last_name: Hüllmann
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Alexander
full_name: Klaas, Alexander
last_name: Klaas
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Sven
full_name: Kurras, Sven
last_name: Kurras
- first_name: Marcus
full_name: Märtens, Marcus
last_name: Märtens
- first_name: Friedhelm Meyer
full_name: auf der Heide, Friedhelm Meyer
last_name: auf der Heide
- first_name: Christoph
full_name: Raupach, Christoph
last_name: Raupach
- first_name: Kamil
full_name: Swierkot, Kamil
last_name: Swierkot
- first_name: Daniel
full_name: Warner, Daniel
id: '3902'
last_name: Warner
- first_name: Christoph
full_name: Weddemann, Christoph
last_name: Weddemann
- first_name: Daniel
full_name: Wonisch, Daniel
last_name: Wonisch
citation:
ama: 'Cord-Landwehr A, Degener B, Fischer M, et al. Collisionless Gathering of Robots
with an Extent. In: SOFSEM 2011: Theory and Practice of Computer Science.
Berlin, Heidelberg; 2011. doi:10.1007/978-3-642-18381-2_15'
apa: 'Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas,
A., … Wonisch, D. (2011). Collisionless Gathering of Robots with an Extent. In
SOFSEM 2011: Theory and Practice of Computer Science. Berlin, Heidelberg.
https://doi.org/10.1007/978-3-642-18381-2_15'
bibtex: '@inbook{Cord-Landwehr_Degener_Fischer_Hüllmann_Kempkes_Klaas_Kling_Kurras_Märtens_auf
der Heide_et al._2011, place={Berlin, Heidelberg}, title={Collisionless Gathering
of Robots with an Extent}, DOI={10.1007/978-3-642-18381-2_15},
booktitle={SOFSEM 2011: Theory and Practice of Computer Science}, author={Cord-Landwehr,
Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes,
Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus
and auf der Heide, Friedhelm Meyer and et al.}, year={2011} }'
chicago: 'Cord-Landwehr, Andreas, Bastian Degener, Matthias Fischer, Martina Hüllmann,
Barbara Kempkes, Alexander Klaas, Peter Kling, et al. “Collisionless Gathering
of Robots with an Extent.” In SOFSEM 2011: Theory and Practice of Computer
Science. Berlin, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-18381-2_15.'
ieee: 'A. Cord-Landwehr et al., “Collisionless Gathering of Robots with an
Extent,” in SOFSEM 2011: Theory and Practice of Computer Science, Berlin,
Heidelberg, 2011.'
mla: 'Cord-Landwehr, Andreas, et al. “Collisionless Gathering of Robots with an
Extent.” SOFSEM 2011: Theory and Practice of Computer Science, 2011, doi:10.1007/978-3-642-18381-2_15.'
short: 'A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas,
P. Kling, S. Kurras, M. Märtens, F.M. auf der Heide, C. Raupach, K. Swierkot,
D. Warner, C. Weddemann, D. Wonisch, in: SOFSEM 2011: Theory and Practice of Computer
Science, Berlin, Heidelberg, 2011.'
date_created: 2020-12-12T11:15:30Z
date_updated: 2022-01-06T06:54:33Z
department:
- _id: '63'
doi: 10.1007/978-3-642-18381-2_15
language:
- iso: eng
place: Berlin, Heidelberg
publication: 'SOFSEM 2011: Theory and Practice of Computer Science'
publication_identifier:
isbn:
- '9783642183805'
- '9783642183812'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Collisionless Gathering of Robots with an Extent
type: book_chapter
user_id: '3902'
year: '2011'
...
---
_id: '20710'
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Matthias
full_name: Fischer, Matthias
last_name: Fischer
- first_name: Martina
full_name: Hüllmann, Martina
last_name: Hüllmann
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Alexander
full_name: Klaas, Alexander
last_name: Klaas
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Sven
full_name: Kurras, Sven
last_name: Kurras
- first_name: Marcus
full_name: Märtens, Marcus
last_name: Märtens
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
last_name: Meyer auf der Heide
- first_name: Christoph
full_name: Raupach, Christoph
last_name: Raupach
- first_name: Kamil
full_name: Swierkot, Kamil
last_name: Swierkot
- first_name: Daniel
full_name: Warner, Daniel
id: '3902'
last_name: Warner
- first_name: Christoph
full_name: Weddemann, Christoph
last_name: Weddemann
- first_name: Daniel
full_name: Wonisch, Daniel
last_name: Wonisch
citation:
ama: 'Cord-Landwehr A, Degener B, Fischer M, et al. A New Approach for Analyzing
Convergence Algorithms for Mobile Robots. In: Automata, Languages and Programming.
Berlin, Heidelberg; 2011. doi:10.1007/978-3-642-22012-8_52'
apa: Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas,
A., … Wonisch, D. (2011). A New Approach for Analyzing Convergence Algorithms
for Mobile Robots. In Automata, Languages and Programming. Berlin, Heidelberg.
https://doi.org/10.1007/978-3-642-22012-8_52
bibtex: '@inbook{Cord-Landwehr_Degener_Fischer_Hüllmann_Kempkes_Klaas_Kling_Kurras_Märtens_Meyer
auf der Heide_et al._2011, place={Berlin, Heidelberg}, title={A New Approach for
Analyzing Convergence Algorithms for Mobile Robots}, DOI={10.1007/978-3-642-22012-8_52},
booktitle={Automata, Languages and Programming}, author={Cord-Landwehr, Andreas
and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes,
Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus
and Meyer auf der Heide, Friedhelm and et al.}, year={2011} }'
chicago: Cord-Landwehr, Andreas, Bastian Degener, Matthias Fischer, Martina Hüllmann,
Barbara Kempkes, Alexander Klaas, Peter Kling, et al. “A New Approach for Analyzing
Convergence Algorithms for Mobile Robots.” In Automata, Languages and Programming.
Berlin, Heidelberg, 2011. https://doi.org/10.1007/978-3-642-22012-8_52.
ieee: A. Cord-Landwehr et al., “A New Approach for Analyzing Convergence
Algorithms for Mobile Robots,” in Automata, Languages and Programming,
Berlin, Heidelberg, 2011.
mla: Cord-Landwehr, Andreas, et al. “A New Approach for Analyzing Convergence Algorithms
for Mobile Robots.” Automata, Languages and Programming, 2011, doi:10.1007/978-3-642-22012-8_52.
short: 'A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas,
P. Kling, S. Kurras, M. Märtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot,
D. Warner, C. Weddemann, D. Wonisch, in: Automata, Languages and Programming,
Berlin, Heidelberg, 2011.'
date_created: 2020-12-12T12:22:41Z
date_updated: 2022-01-06T06:54:33Z
department:
- _id: '63'
doi: 10.1007/978-3-642-22012-8_52
language:
- iso: eng
place: Berlin, Heidelberg
publication: Automata, Languages and Programming
publication_identifier:
isbn:
- '9783642220111'
- '9783642220128'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: A New Approach for Analyzing Convergence Algorithms for Mobile Robots
type: book_chapter
user_id: '3902'
year: '2011'
...
---
_id: '18193'
author:
- first_name: Hendrik
full_name: Renken, Hendrik
last_name: Renken
- first_name: Christoph
full_name: Laroque, Christoph
last_name: Laroque
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
citation:
ama: 'Renken H, Laroque C, Fischer M. An Easy Extendable Modeling Framework for
Discrete Event Simulation Models and their Visualization. In: Proceedings of
The 25th European Simulation and Modelling Conference - ESM2011. ; 2011.'
apa: Renken, H., Laroque, C., & Fischer, M. (2011). An Easy Extendable Modeling
Framework for Discrete Event Simulation Models and their Visualization. In Proceedings
of The 25th European Simulation and Modelling Conference - ESM2011.
bibtex: '@inproceedings{Renken_Laroque_Fischer_2011, title={An Easy Extendable Modeling
Framework for Discrete Event Simulation Models and their Visualization}, booktitle={Proceedings
of The 25th European Simulation and Modelling Conference - ESM2011}, author={Renken,
Hendrik and Laroque, Christoph and Fischer, Matthias}, year={2011} }'
chicago: Renken, Hendrik, Christoph Laroque, and Matthias Fischer. “An Easy Extendable
Modeling Framework for Discrete Event Simulation Models and Their Visualization.”
In Proceedings of The 25th European Simulation and Modelling Conference - ESM2011,
2011.
ieee: H. Renken, C. Laroque, and M. Fischer, “An Easy Extendable Modeling Framework
for Discrete Event Simulation Models and their Visualization,” in Proceedings
of The 25th European Simulation and Modelling Conference - ESM2011, 2011.
mla: Renken, Hendrik, et al. “An Easy Extendable Modeling Framework for Discrete
Event Simulation Models and Their Visualization.” Proceedings of The 25th European
Simulation and Modelling Conference - ESM2011, 2011.
short: 'H. Renken, C. Laroque, M. Fischer, in: Proceedings of The 25th European
Simulation and Modelling Conference - ESM2011, 2011.'
date_created: 2020-08-24T14:01:49Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '63'
language:
- iso: eng
publication: Proceedings of The 25th European Simulation and Modelling Conference
- ESM2011
status: public
title: An Easy Extendable Modeling Framework for Discrete Event Simulation Models
and their Visualization
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '18194'
abstract:
- lang: eng
text: 'We present a parallel rendering system for PC-Clusters to visualize large
3D scenes. One single visualization node, equipped with a high-end graphics adapter,
is supported by a group of backend nodes with weak graphics performance. The objects
of the scene are distributed among these backend nodes, they serve two purposes:
First, they provide an out-of-core memory system for the visualization node. Second,
they assist the visualization node''s rendering by performing visibility calculations
and only sending visible objects to the visualization node. In order to obtain
fast rendering with our system, we have to distribute the objects among the backend
nodes in a way that does not only guarantee an even distribution of the objects,
but also an even distribution of the visibility calculations and the amount of
data send to the visualization node. We identify necessary properties of the distribution
and argue that a random distribution is a good candidate. Further, in order to
reduce the number of objects sent to the visualization node per frame, we employ
an approximate hierarchical occlusion culling in each backend node. For this,
they are equipped, in addition to the objects assigned to them, with simplified
versions of the other objects of the 3D scene. The visualization node is equipped
with 512 MiB video memory and supported by 15 backend nodes. This system is able
to render a approx. 350 million polygons (approx. 8.5 GiB) large aircraft model
between 20 - 30 fps and thus allows a walkthrough in real-time.'
author:
- first_name: Tim
full_name: Suess, Tim
last_name: Suess
- first_name: Clemens
full_name: Koch, Clemens
last_name: Koch
- 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: Suess T, Koch C, Jähn C, Fischer M, Meyer auf der Heide F. Parallel Out-of-Core
Occlusion Culling. Published online 2011.
apa: Suess, T., Koch, C., Jähn, C., Fischer, M., & Meyer auf der Heide, F. (2011).
Parallel Out-of-Core Occlusion Culling.
bibtex: '@article{Suess_Koch_Jähn_Fischer_Meyer auf der Heide_2011, title={Parallel
Out-of-Core Occlusion Culling}, author={Suess, Tim and Koch, Clemens and Jähn,
Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm}, year={2011}
}'
chicago: Suess, Tim, Clemens Koch, Claudius Jähn, Matthias Fischer, and Friedhelm
Meyer auf der Heide. “Parallel Out-of-Core Occlusion Culling,” 2011.
ieee: T. Suess, C. Koch, C. Jähn, M. Fischer, and F. Meyer auf der Heide, “Parallel
Out-of-Core Occlusion Culling.” 2011.
mla: Suess, Tim, et al. Parallel Out-of-Core Occlusion Culling. 2011.
short: T. Suess, C. Koch, C. Jähn, M. Fischer, F. Meyer auf der Heide, (2011).
date_created: 2020-08-24T14:14:10Z
date_updated: 2022-01-06T06:53:27Z
ddc:
- '000'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: koala
date_created: 2020-08-24T14:13:46Z
date_updated: 2020-08-24T14:13:46Z
file_id: '18195'
file_name: pre-03-2011-5220.pdf
file_size: 3091853
relation: main_file
success: 1
file_date_updated: 2020-08-24T14:13:46Z
has_accepted_license: '1'
language:
- iso: eng
status: public
title: Parallel Out-of-Core Occlusion Culling
type: preprint
user_id: '15415'
year: '2011'
...
---
_id: '18568'
author:
- first_name: Berthold
full_name: Vöcking, Berthold
last_name: Vöcking
- first_name: Martin
full_name: Hoefer, Martin
last_name: Hoefer
- first_name: 'Alexander '
full_name: 'Skopalik, Alexander '
last_name: Skopalik
- first_name: Michal
full_name: Penn, Michal
last_name: Penn
- first_name: Maria
full_name: Polukarov, Maria
last_name: Polukarov
citation:
ama: 'Vöcking B, Hoefer M, Skopalik A, Penn M, Polukarov M. Considerate Equilibrium.
In: {IJCAI} 2011, Proceedings of the 22nd International Joint Conference on
Artificial Intelligence,. ; 2011:234--239.'
apa: Vöcking, B., Hoefer, M., Skopalik, A., Penn, M., & Polukarov, M. (2011).
Considerate Equilibrium. In {IJCAI} 2011, Proceedings of the 22nd International
Joint Conference on Artificial Intelligence, (pp. 234--239).
bibtex: '@inproceedings{Vöcking_Hoefer_Skopalik_Penn_Polukarov_2011, title={Considerate
Equilibrium}, booktitle={{IJCAI} 2011, Proceedings of the 22nd International Joint
Conference on Artificial Intelligence,}, author={Vöcking, Berthold and Hoefer,
Martin and Skopalik, Alexander and Penn, Michal and Polukarov, Maria}, year={2011},
pages={234--239} }'
chicago: Vöcking, Berthold, Martin Hoefer, Alexander Skopalik, Michal Penn, and
Maria Polukarov. “Considerate Equilibrium.” In {IJCAI} 2011, Proceedings of
the 22nd International Joint Conference on Artificial Intelligence, 234--239,
2011.
ieee: B. Vöcking, M. Hoefer, A. Skopalik, M. Penn, and M. Polukarov, “Considerate
Equilibrium,” in {IJCAI} 2011, Proceedings of the 22nd International Joint
Conference on Artificial Intelligence, 2011, pp. 234--239.
mla: Vöcking, Berthold, et al. “Considerate Equilibrium.” {IJCAI} 2011, Proceedings
of the 22nd International Joint Conference on Artificial Intelligence, 2011,
pp. 234--239.
short: 'B. Vöcking, M. Hoefer, A. Skopalik, M. Penn, M. Polukarov, in: {IJCAI} 2011,
Proceedings of the 22nd International Joint Conference on Artificial Intelligence,
2011, pp. 234--239.'
date_created: 2020-08-28T12:23:42Z
date_updated: 2022-01-06T06:53:40Z
department:
- _id: '63'
language:
- iso: eng
page: 234--239
publication: '{IJCAI} 2011, Proceedings of the 22nd International Joint Conference
on Artificial Intelligence,'
related_material:
link:
- relation: confirmation
url: http://ijcai.org/papers11/Papers/IJCAI11-050.pdf
status: public
title: Considerate Equilibrium
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '657'
abstract:
- lang: eng
text: 'We present two distributed, constant factor approximation algorithms for
the metric facility location problem. Both algorithms have been designed with
a strong emphasis on applicability in the area of wireless sensor networks: in
order to execute them, each sensor node only requires limited local knowledge
and simple computations. Also, the algorithms can cope with measurement errors
and take into account that communication costs between sensor nodes do not necessarily
increase linearly with the distance, but can be represented by a polynomial. Since
it cannot always be expected that sensor nodes execute algorithms in a synchronized
way, our algorithms are executed in an asynchronous model (but they are still
able to break symmetry that might occur when two neighboring nodes act at exactly
the same time). Furthermore, they can deal with dynamic scenarios: if a node moves,
the solution is updated and the update affects only nodes in the local neighborhood.
Finally, the algorithms are robust in the sense that incorrect behavior of some
nodes during some round will, in the end, still result in a good approximation.
The first algorithm runs in expected O(log_{1+\epsilon} n) communication rounds
and yields a \my^4(1+4\my^2(1+\epsilon)^{1/p})^p approximation, while the second
has a running time of expected O(log^2_{1+\epsilon} n) communication rounds and
an approximation factor of \my^4(1 + 2(1 + \epsilon)^{1/p})^p. Here, \epsilon
> 0 is an arbitrarily small constant, p the exponent of the polynomial representing
the communication costs, and \my the relative measurement error.'
author:
- first_name: Sebastan
full_name: Abshoff, Sebastan
last_name: Abshoff
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: 'Barbara '
full_name: 'Kempkes, Barbara '
last_name: Kempkes
- first_name: Peter
full_name: Pietrzyk, Peter
last_name: Pietrzyk
citation:
ama: 'Abshoff S, Cord-Landwehr A, Degener B, Kempkes B, Pietrzyk P. Local Approximation
Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware
Sensor Networks. In: Proceedings of the 7th International Symposium on Algorithms
for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS).
LNCS. ; 2011:13-27. doi:10.1007/978-3-642-28209-6_3'
apa: Abshoff, S., Cord-Landwehr, A., Degener, B., Kempkes, B., & Pietrzyk, P.
(2011). Local Approximation Algorithms for the Uncapacitated Metric Facility Location
Problem in Power-Aware Sensor Networks. In Proceedings of the 7th International
Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous
Mobile Entities (ALGOSENSORS) (pp. 13–27). https://doi.org/10.1007/978-3-642-28209-6_3
bibtex: '@inproceedings{Abshoff_Cord-Landwehr_Degener_Kempkes_Pietrzyk_2011, series={LNCS},
title={Local Approximation Algorithms for the Uncapacitated Metric Facility Location
Problem in Power-Aware Sensor Networks}, DOI={10.1007/978-3-642-28209-6_3},
booktitle={Proceedings of the 7th International Symposium on Algorithms for Sensor
Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)},
author={Abshoff, Sebastan and Cord-Landwehr, Andreas and Degener, Bastian and
Kempkes, Barbara and Pietrzyk, Peter}, year={2011}, pages={13–27}, collection={LNCS}
}'
chicago: Abshoff, Sebastan, Andreas Cord-Landwehr, Bastian Degener, Barbara Kempkes,
and Peter Pietrzyk. “Local Approximation Algorithms for the Uncapacitated Metric
Facility Location Problem in Power-Aware Sensor Networks.” In Proceedings of
the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad
Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), 13–27. LNCS, 2011.
https://doi.org/10.1007/978-3-642-28209-6_3.
ieee: S. Abshoff, A. Cord-Landwehr, B. Degener, B. Kempkes, and P. Pietrzyk, “Local
Approximation Algorithms for the Uncapacitated Metric Facility Location Problem
in Power-Aware Sensor Networks,” in Proceedings of the 7th International Symposium
on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile
Entities (ALGOSENSORS), 2011, pp. 13–27.
mla: Abshoff, Sebastan, et al. “Local Approximation Algorithms for the Uncapacitated
Metric Facility Location Problem in Power-Aware Sensor Networks.” Proceedings
of the 7th International Symposium on Algorithms for Sensor Systems, Wireless
Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), 2011, pp. 13–27,
doi:10.1007/978-3-642-28209-6_3.
short: 'S. Abshoff, A. Cord-Landwehr, B. Degener, B. Kempkes, P. Pietrzyk, in: Proceedings
of the 7th International Symposium on Algorithms for Sensor Systems, Wireless
Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), 2011, pp. 13–27.'
date_created: 2017-10-17T12:43:00Z
date_updated: 2022-01-06T07:03:12Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-28209-6_3
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-14T13:48:21Z
date_updated: 2018-03-14T13:48:21Z
file_id: '1219'
file_name: 657-flp_algosensors2011-Cord-Landwehr.pdf
file_size: 454740
relation: main_file
success: 1
file_date_updated: 2018-03-14T13:48:21Z
has_accepted_license: '1'
language:
- iso: eng
page: 13-27
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 7th International Symposium on Algorithms for Sensor
Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)
series_title: LNCS
status: public
title: Local Approximation Algorithms for the Uncapacitated Metric Facility Location
Problem in Power-Aware Sensor Networks
type: conference
user_id: '477'
year: '2011'
...
---
_id: '663'
author:
- first_name: Kamil
full_name: Swierkot, Kamil
last_name: Swierkot
citation:
ama: Swierkot K. Complexity Classes for Local Computation. Universität Paderborn;
2011.
apa: Swierkot, K. (2011). Complexity Classes for Local Computation. Universität
Paderborn.
bibtex: '@book{Swierkot_2011, title={Complexity Classes for Local Computation},
publisher={Universität Paderborn}, author={Swierkot, Kamil}, year={2011} }'
chicago: Swierkot, Kamil. Complexity Classes for Local Computation. Universität
Paderborn, 2011.
ieee: K. Swierkot, Complexity Classes for Local Computation. Universität
Paderborn, 2011.
mla: Swierkot, Kamil. Complexity Classes for Local Computation. Universität
Paderborn, 2011.
short: K. Swierkot, Complexity Classes for Local Computation, Universität Paderborn,
2011.
date_created: 2017-10-17T12:43:01Z
date_updated: 2022-01-06T07:03:13Z
department:
- _id: '63'
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Complexity Classes for Local Computation
type: mastersthesis
user_id: '477'
year: '2011'
...
---
_id: '664'
abstract:
- lang: eng
text: 'Web Computing is a variant of parallel computing where the idle times of
PCs donated by worldwide distributed users are employed to execute parallel programs.
The PUB-Web library developed by us supports this kind of usage of computing resources.
A major problem for the efficient execution of such parallel programs is load
balancing. In the Web Computing context, this problem becomes more difficult because
of the dynamic behavior of the underlying "parallel computer": the set of available
processors (donated PCs) as well as their availability (idle times) change over
time in an unpredictable fashion.In this paper, we experimentally evaluate and
compare load balancing algorithms in this scenario, namely a variant of the well-established
Work Stealing algorithm and strategies based on a heterogeneous version of distributed
hash-tables (DHHTs) introduced recently. In order to run a meaningful experimental
evaluation, we employ, in addition to our Web Computing library PUB-Web, realistic
data sets for the job input streams and for the dynamics of the availability of
the resources.Our experimental evaluations suggest that Work Stealing is the better
strategy if the number of processes ready to run matches the number of available
processors. But a suitable variant of DHHTs outperforms Work Stealing if there
are significantly more processes ready to run than available processors.'
author:
- first_name: Joachim
full_name: Gehweiler, Joachim
last_name: Gehweiler
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Gehweiler J, Kling P, Meyer auf der Heide F. An Experimental Comparison of
Load Balancing Strategies in a Web Computing Environment. In: Proceedings of
the 9th International Conference on Parallel Processing and Applied Mathematics
(PPAM). LNCS. ; 2011:31--40. doi:10.1007/978-3-642-31500-8_4'
apa: Gehweiler, J., Kling, P., & Meyer auf der Heide, F. (2011). An Experimental
Comparison of Load Balancing Strategies in a Web Computing Environment. In Proceedings
of the 9th International Conference on Parallel Processing and Applied Mathematics
(PPAM) (pp. 31--40). https://doi.org/10.1007/978-3-642-31500-8_4
bibtex: '@inproceedings{Gehweiler_Kling_Meyer auf der Heide_2011, series={LNCS},
title={An Experimental Comparison of Load Balancing Strategies in a Web Computing
Environment}, DOI={10.1007/978-3-642-31500-8_4},
booktitle={Proceedings of the 9th International Conference on Parallel Processing
and Applied Mathematics (PPAM)}, author={Gehweiler, Joachim and Kling, Peter and
Meyer auf der Heide, Friedhelm}, year={2011}, pages={31--40}, collection={LNCS}
}'
chicago: Gehweiler, Joachim, Peter Kling, and Friedhelm Meyer auf der Heide. “An
Experimental Comparison of Load Balancing Strategies in a Web Computing Environment.”
In Proceedings of the 9th International Conference on Parallel Processing and
Applied Mathematics (PPAM), 31--40. LNCS, 2011. https://doi.org/10.1007/978-3-642-31500-8_4.
ieee: J. Gehweiler, P. Kling, and F. Meyer auf der Heide, “An Experimental Comparison
of Load Balancing Strategies in a Web Computing Environment,” in Proceedings
of the 9th International Conference on Parallel Processing and Applied Mathematics
(PPAM), 2011, pp. 31--40.
mla: Gehweiler, Joachim, et al. “An Experimental Comparison of Load Balancing Strategies
in a Web Computing Environment.” Proceedings of the 9th International Conference
on Parallel Processing and Applied Mathematics (PPAM), 2011, pp. 31--40, doi:10.1007/978-3-642-31500-8_4.
short: 'J. Gehweiler, P. Kling, F. Meyer auf der Heide, in: Proceedings of the 9th
International Conference on Parallel Processing and Applied Mathematics (PPAM),
2011, pp. 31--40.'
date_created: 2017-10-17T12:43:01Z
date_updated: 2022-01-06T07:03:14Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-31500-8_4
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-14T13:45:57Z
date_updated: 2018-03-14T13:45:57Z
file_id: '1216'
file_name: 664-PPAM11GKM_01.pdf
file_size: 333335
relation: main_file
success: 1
file_date_updated: 2018-03-14T13:45:57Z
has_accepted_license: '1'
page: 31--40
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '14'
name: SFB 901 - Subproject C2
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 9th International Conference on Parallel Processing
and Applied Mathematics (PPAM)
series_title: LNCS
status: public
title: An Experimental Comparison of Load Balancing Strategies in a Web Computing
Environment
type: conference
user_id: '15504'
year: '2011'
...
---
_id: '667'
citation:
ama: Meyer auf der Heide F, Rajaraman R, eds. 23rd Annual ACM Symposium on Parallelism
in Algorithms and Architectures.; 2011. doi:10.1145/1989493
apa: Meyer auf der Heide, F., & Rajaraman, R. (Eds.). (2011). 23rd Annual
ACM Symposium on Parallelism in Algorithms and Architectures. https://doi.org/10.1145/1989493
bibtex: '@book{Meyer auf der Heide_Rajaraman_2011, title={23rd Annual ACM Symposium
on Parallelism in Algorithms and Architectures}, DOI={10.1145/1989493},
year={2011} }'
chicago: Meyer auf der Heide, Friedhelm, and Rajmohan Rajaraman, eds. 23rd Annual
ACM Symposium on Parallelism in Algorithms and Architectures, 2011. https://doi.org/10.1145/1989493.
ieee: F. Meyer auf der Heide and R. Rajaraman, Eds., 23rd Annual ACM Symposium
on Parallelism in Algorithms and Architectures. 2011.
mla: Meyer auf der Heide, Friedhelm, and Rajmohan Rajaraman, editors. 23rd Annual
ACM Symposium on Parallelism in Algorithms and Architectures. 2011, doi:10.1145/1989493.
short: F. Meyer auf der Heide, R. Rajaraman, eds., 23rd Annual ACM Symposium on
Parallelism in Algorithms and Architectures, 2011.
date_created: 2017-10-17T12:43:02Z
date_updated: 2022-01-06T07:03:14Z
department:
- _id: '63'
doi: 10.1145/1989493
editor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: 'Rajmohan '
full_name: 'Rajaraman, Rajmohan '
last_name: Rajaraman
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
status: public
title: 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures
type: conference_editor
user_id: '477'
year: '2011'
...
---
_id: '16410'
abstract:
- lang: eng
text: 'Gathering n mobile robots in one single point in the Euclidean plane is a
widely studied problem from the area of robot formation problems. Classically,
the robots are assumed to have no physical extent, and they are able to share
a position with other robots. We drop these assumptions and investigate a similar
problem for robots with (a spherical) extent: the goal is to gather the robots
as close together as possible. More exactly, we want the robots to form a sphere
with minimum radius around a predefined point. We propose an algorithm for this
problem which synchronously moves the robots towards the center of the sphere
unless they block each other. In this case, if possible, the robots spin around
the center of the sphere. We analyze this algorithm experimentally in the plane.
If R is the distance of the farthest robot to the center of the sphere, the simulations
indicate a runtime which is linear in n and R. Additionally, we prove a theoretic
upper bound for the runtime of O(nR) for a discrete version of the problem. Simulations
also suggest a runtime of O(n + R) for the discrete version.'
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Martina
full_name: Hüllmann, Martina
last_name: Hüllmann
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Alexander
full_name: Klaas, Alexander
last_name: Klaas
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Sven
full_name: Kurras, Sven
last_name: Kurras
- first_name: Marcus
full_name: Märtens, Marcus
last_name: Märtens
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christoph
full_name: Raupach, Christoph
last_name: Raupach
- first_name: Kamil
full_name: Swierkot, Kamil
last_name: Swierkot
- first_name: Daniel
full_name: Warner, Daniel
last_name: Warner
- first_name: Christoph
full_name: Weddemann, Christoph
last_name: Weddemann
- first_name: Daniel
full_name: Wonisch, Daniel
last_name: Wonisch
citation:
ama: 'Cord-Landwehr A, Degener B, Fischer M, et al. Collisionless Gathering of Robots
with an Extent. In: 37th International Conference on Current Trends in Theory
and Practice of Computer Science (SOFSEM 2011). Springer; 2011:178-189. doi:10.1007/978-3-642-18381-2_15'
apa: Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas,
A., … Wonisch, D. (2011). Collisionless Gathering of Robots with an Extent. In
37th International Conference on Current Trends in Theory and Practice of Computer
Science (SOFSEM 2011) (pp. 178–189). Springer. https://doi.org/10.1007/978-3-642-18381-2_15
bibtex: '@inproceedings{Cord-Landwehr_Degener_Fischer_Hüllmann_Kempkes_Klaas_Kling_Kurras_Märtens_Meyer
auf der Heide_et al._2011, title={Collisionless Gathering of Robots with an Extent},
DOI={10.1007/978-3-642-18381-2_15},
number={6543}, booktitle={37th International Conference on Current Trends in Theory
and Practice of Computer Science (SOFSEM 2011)}, publisher={Springer}, author={Cord-Landwehr,
Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes,
Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus
and Meyer auf der Heide, Friedhelm and et al.}, year={2011}, pages={178–189} }'
chicago: Cord-Landwehr, Andreas, Bastian Degener, Matthias Fischer, Martina Hüllmann,
Barbara Kempkes, Alexander Klaas, Peter Kling, et al. “Collisionless Gathering
of Robots with an Extent.” In 37th International Conference on Current Trends
in Theory and Practice of Computer Science (SOFSEM 2011), 178–89. Springer,
2011. https://doi.org/10.1007/978-3-642-18381-2_15.
ieee: A. Cord-Landwehr et al., “Collisionless Gathering of Robots with an
Extent,” in 37th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM 2011), 2011, no. 6543, pp. 178–189.
mla: Cord-Landwehr, Andreas, et al. “Collisionless Gathering of Robots with an Extent.”
37th International Conference on Current Trends in Theory and Practice of Computer
Science (SOFSEM 2011), no. 6543, Springer, 2011, pp. 178–89, doi:10.1007/978-3-642-18381-2_15.
short: 'A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas,
P. Kling, S. Kurras, M. Märtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot,
D. Warner, C. Weddemann, D. Wonisch, in: 37th International Conference on Current
Trends in Theory and Practice of Computer Science (SOFSEM 2011), Springer, 2011,
pp. 178–189.'
date_created: 2020-04-06T07:52:42Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-18381-2_15
issue: '6543'
language:
- iso: eng
page: 178-189
publication: 37th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM 2011)
publication_identifier:
isbn:
- '9783642183805'
- '9783642183812'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer
status: public
title: Collisionless Gathering of Robots with an Extent
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '16412'
author:
- first_name: Joachim
full_name: Gehweiler, Joachim
last_name: Gehweiler
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Gehweiler J, Meyer auf der Heide F. Bin Packing - How Do I Get My Stuff into
the Boxes. In: Algorithms Unplugged. Berlin, Heidelberg; 2011:367-374.
doi:10.1007/978-3-642-15328-0_38'
apa: Gehweiler, J., & Meyer auf der Heide, F. (2011). Bin Packing - How Do I
Get My Stuff into the Boxes. In Algorithms Unplugged (pp. 367–374). Berlin,
Heidelberg. https://doi.org/10.1007/978-3-642-15328-0_38
bibtex: '@inbook{Gehweiler_Meyer auf der Heide_2011, place={Berlin, Heidelberg},
title={Bin Packing - How Do I Get My Stuff into the Boxes}, DOI={10.1007/978-3-642-15328-0_38},
booktitle={Algorithms Unplugged}, author={Gehweiler, Joachim and Meyer auf der
Heide, Friedhelm}, year={2011}, pages={367–374} }'
chicago: Gehweiler, Joachim, and Friedhelm Meyer auf der Heide. “Bin Packing - How
Do I Get My Stuff into the Boxes.” In Algorithms Unplugged, 367–74. Berlin,
Heidelberg, 2011. https://doi.org/10.1007/978-3-642-15328-0_38.
ieee: J. Gehweiler and F. Meyer auf der Heide, “Bin Packing - How Do I Get My Stuff
into the Boxes,” in Algorithms Unplugged, Berlin, Heidelberg, 2011, pp.
367–374.
mla: Gehweiler, Joachim, and Friedhelm Meyer auf der Heide. “Bin Packing - How Do
I Get My Stuff into the Boxes.” Algorithms Unplugged, 2011, pp. 367–74,
doi:10.1007/978-3-642-15328-0_38.
short: 'J. Gehweiler, F. Meyer auf der Heide, in: Algorithms Unplugged, Berlin,
Heidelberg, 2011, pp. 367–374.'
date_created: 2020-04-06T10:10:39Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-642-15328-0_38
language:
- iso: eng
page: 367-374
place: Berlin, Heidelberg
publication: Algorithms Unplugged
publication_identifier:
isbn:
- '9783642153273'
- '9783642153280'
publication_status: published
status: public
title: Bin Packing - How Do I Get My Stuff into the Boxes
type: book_chapter
user_id: '15415'
year: '2011'
...
---
_id: '16428'
author:
- first_name: Rajmohan
full_name: Rajaraman, Rajmohan
last_name: Rajaraman
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Rajaraman R, Meyer auf der Heide F. Proceedings of the 23rd ACM symposium
on Parallelism in algorithms and architectures - SPAA ’11. In: ; 2011. doi:10.1145/1989493'
apa: Rajaraman, R., & Meyer auf der Heide, F. (2011). Proceedings of the 23rd
ACM symposium on Parallelism in algorithms and architectures - SPAA ’11. https://doi.org/10.1145/1989493
bibtex: '@inproceedings{Rajaraman_Meyer auf der Heide_2011, title={Proceedings of
the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA ’11},
DOI={10.1145/1989493}, author={Rajaraman,
Rajmohan and Meyer auf der Heide, Friedhelm}, year={2011} }'
chicago: Rajaraman, Rajmohan, and Friedhelm Meyer auf der Heide. “Proceedings of
the 23rd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’11,”
2011. https://doi.org/10.1145/1989493.
ieee: R. Rajaraman and F. Meyer auf der Heide, “Proceedings of the 23rd ACM symposium
on Parallelism in algorithms and architectures - SPAA ’11,” 2011.
mla: Rajaraman, Rajmohan, and Friedhelm Meyer auf der Heide. Proceedings of the
23rd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’11.
2011, doi:10.1145/1989493.
short: 'R. Rajaraman, F. Meyer auf der Heide, in: 2011.'
date_created: 2020-04-06T13:48:10Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1145/1989493
language:
- iso: eng
publication_identifier:
isbn:
- '9781450307437'
publication_status: published
status: public
title: Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures
- SPAA '11
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '16447'
author:
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Sándor P.
full_name: Fekete, Sándor P.
last_name: Fekete
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Degener B, Fekete SP, Kempkes B, Meyer auf der Heide F. A survey on relay placement
with runtime and approximation guarantees. Computer Science Review. 2011:57-68.
doi:10.1016/j.cosrev.2010.09.005
apa: Degener, B., Fekete, S. P., Kempkes, B., & Meyer auf der Heide, F. (2011).
A survey on relay placement with runtime and approximation guarantees. Computer
Science Review, 57–68. https://doi.org/10.1016/j.cosrev.2010.09.005
bibtex: '@article{Degener_Fekete_Kempkes_Meyer auf der Heide_2011, title={A survey
on relay placement with runtime and approximation guarantees}, DOI={10.1016/j.cosrev.2010.09.005},
journal={Computer Science Review}, author={Degener, Bastian and Fekete, Sándor
P. and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}, year={2011}, pages={57–68}
}'
chicago: Degener, Bastian, Sándor P. Fekete, Barbara Kempkes, and Friedhelm Meyer
auf der Heide. “A Survey on Relay Placement with Runtime and Approximation Guarantees.”
Computer Science Review, 2011, 57–68. https://doi.org/10.1016/j.cosrev.2010.09.005.
ieee: B. Degener, S. P. Fekete, B. Kempkes, and F. Meyer auf der Heide, “A survey
on relay placement with runtime and approximation guarantees,” Computer Science
Review, pp. 57–68, 2011.
mla: Degener, Bastian, et al. “A Survey on Relay Placement with Runtime and Approximation
Guarantees.” Computer Science Review, 2011, pp. 57–68, doi:10.1016/j.cosrev.2010.09.005.
short: B. Degener, S.P. Fekete, B. Kempkes, F. Meyer auf der Heide, Computer Science
Review (2011) 57–68.
date_created: 2020-04-07T06:46:06Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1016/j.cosrev.2010.09.005
language:
- iso: eng
page: 57-68
publication: Computer Science Review
publication_identifier:
issn:
- 1574-0137
publication_status: published
status: public
title: A survey on relay placement with runtime and approximation guarantees
type: journal_article
user_id: '15415'
year: '2011'
...
---
_id: '16451'
author:
- first_name: Philipp
full_name: Brandes, Philipp
last_name: Brandes
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Brandes P, Degener B, Kempkes B, Meyer auf der Heide F. Energy-efficient strategies
for building short chains of mobile robots locally. In: SIROCCO ’11: Proc.
of the 18th International Colloquium on Structural Information and Communication
Complexity. ; 2011:138-149. doi:10.1016/j.tcs.2012.10.056'
apa: 'Brandes, P., Degener, B., Kempkes, B., & Meyer auf der Heide, F. (2011).
Energy-efficient strategies for building short chains of mobile robots locally.
In SIROCCO ’11: Proc. of the 18th International Colloquium on Structural Information
and Communication Complexity (pp. 138–149). https://doi.org/10.1016/j.tcs.2012.10.056'
bibtex: '@inproceedings{Brandes_Degener_Kempkes_Meyer auf der Heide_2011, title={Energy-efficient
strategies for building short chains of mobile robots locally}, DOI={10.1016/j.tcs.2012.10.056},
booktitle={SIROCCO ’11: Proc. of the 18th International Colloquium on Structural
Information and Communication Complexity}, author={Brandes, Philipp and Degener,
Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}, year={2011},
pages={138–149} }'
chicago: 'Brandes, Philipp, Bastian Degener, Barbara Kempkes, and Friedhelm Meyer
auf der Heide. “Energy-Efficient Strategies for Building Short Chains of Mobile
Robots Locally.” In SIROCCO ’11: Proc. of the 18th International Colloquium
on Structural Information and Communication Complexity, 138–49, 2011. https://doi.org/10.1016/j.tcs.2012.10.056.'
ieee: 'P. Brandes, B. Degener, B. Kempkes, and F. Meyer auf der Heide, “Energy-efficient
strategies for building short chains of mobile robots locally,” in SIROCCO
’11: Proc. of the 18th International Colloquium on Structural Information and
Communication Complexity, 2011, pp. 138–149.'
mla: 'Brandes, Philipp, et al. “Energy-Efficient Strategies for Building Short Chains
of Mobile Robots Locally.” SIROCCO ’11: Proc. of the 18th International Colloquium
on Structural Information and Communication Complexity, 2011, pp. 138–49,
doi:10.1016/j.tcs.2012.10.056.'
short: 'P. Brandes, B. Degener, B. Kempkes, F. Meyer auf der Heide, in: SIROCCO
’11: Proc. of the 18th International Colloquium on Structural Information and
Communication Complexity, 2011, pp. 138–149.'
date_created: 2020-04-07T12:12:23Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1016/j.tcs.2012.10.056
language:
- iso: eng
page: 138-149
publication: 'SIROCCO ''11: Proc. of the 18th International Colloquium on Structural
Information and Communication Complexity'
publication_status: published
status: public
title: Energy-efficient strategies for building short chains of mobile robots locally
type: conference
user_id: '15415'
year: '2011'
...
---
_id: '16453'
author:
- first_name: Bastian
full_name: Degener, Bastian
last_name: Degener
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
- first_name: Tobias
full_name: Langner, Tobias
last_name: Langner
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Peter
full_name: Pietrzyk, Peter
last_name: Pietrzyk
- first_name: Roger
full_name: Wattenhofer, Roger
last_name: Wattenhofer
citation:
ama: 'Degener B, Kempkes B, Langner T, Meyer auf der Heide F, Pietrzyk P, Wattenhofer
R. A tight runtime bound for synchronous gathering of autonomous robots with limited
visibility. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms
and Architectures - SPAA ’11. ; 2011. doi:10.1145/1989493.1989515'
apa: Degener, B., Kempkes, B., Langner, T., Meyer auf der Heide, F., Pietrzyk, P.,
& Wattenhofer, R. (2011). A tight runtime bound for synchronous gathering
of autonomous robots with limited visibility. In Proceedings of the 23rd ACM
symposium on Parallelism in algorithms and architectures - SPAA ’11. https://doi.org/10.1145/1989493.1989515
bibtex: '@inproceedings{Degener_Kempkes_Langner_Meyer auf der Heide_Pietrzyk_Wattenhofer_2011,
title={A tight runtime bound for synchronous gathering of autonomous robots with
limited visibility}, DOI={10.1145/1989493.1989515},
booktitle={Proceedings of the 23rd ACM symposium on Parallelism in algorithms
and architectures - SPAA ’11}, author={Degener, Bastian and Kempkes, Barbara and
Langner, Tobias and Meyer auf der Heide, Friedhelm and Pietrzyk, Peter and Wattenhofer,
Roger}, year={2011} }'
chicago: Degener, Bastian, Barbara Kempkes, Tobias Langner, Friedhelm Meyer auf
der Heide, Peter Pietrzyk, and Roger Wattenhofer. “A Tight Runtime Bound for Synchronous
Gathering of Autonomous Robots with Limited Visibility.” In Proceedings of
the 23rd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’11,
2011. https://doi.org/10.1145/1989493.1989515.
ieee: B. Degener, B. Kempkes, T. Langner, F. Meyer auf der Heide, P. Pietrzyk, and
R. Wattenhofer, “A tight runtime bound for synchronous gathering of autonomous
robots with limited visibility,” in Proceedings of the 23rd ACM symposium on
Parallelism in algorithms and architectures - SPAA ’11, 2011.
mla: Degener, Bastian, et al. “A Tight Runtime Bound for Synchronous Gathering of
Autonomous Robots with Limited Visibility.” Proceedings of the 23rd ACM Symposium
on Parallelism in Algorithms and Architectures - SPAA ’11, 2011, doi:10.1145/1989493.1989515.
short: 'B. Degener, B. Kempkes, T. Langner, F. Meyer auf der Heide, P. Pietrzyk,
R. Wattenhofer, in: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms
and Architectures - SPAA ’11, 2011.'
date_created: 2020-04-07T12:31:24Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1145/1989493.1989515
language:
- iso: eng
publication: Proceedings of the 23rd ACM symposium on Parallelism in algorithms and
architectures - SPAA '11
publication_identifier:
isbn:
- '9781450307437'
publication_status: published
status: public
title: A tight runtime bound for synchronous gathering of autonomous robots with limited
visibility
type: conference
user_id: '15415'
year: '2011'
...