---
_id: '33947'
article_type: original
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Jonas
full_name: Harbig, Jonas
id: '47213'
last_name: Harbig
- first_name: Daniel
full_name: Jung, Daniel
id: '37827'
last_name: Jung
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Castenow J, Harbig J, Jung D, Knollmann T, Meyer auf der Heide F. Gathering
a Euclidean Closed Chain of Robots in Linear Time and Improved Algorithms for
Chain-Formation. Theoretical Computer Science. 2023;939:261-291. doi:10.1016/j.tcs.2022.10.031
apa: Castenow, J., Harbig, J., Jung, D., Knollmann, T., & Meyer auf der Heide,
F. (2023). Gathering a Euclidean Closed Chain of Robots in Linear Time and Improved
Algorithms for Chain-Formation. Theoretical Computer Science, 939,
261–291. https://doi.org/10.1016/j.tcs.2022.10.031
bibtex: '@article{Castenow_Harbig_Jung_Knollmann_Meyer auf der Heide_2023, title={Gathering
a Euclidean Closed Chain of Robots in Linear Time and Improved Algorithms for
Chain-Formation}, volume={939}, DOI={10.1016/j.tcs.2022.10.031},
journal={Theoretical Computer Science}, publisher={Elsevier BV}, author={Castenow,
Jannik and Harbig, Jonas and Jung, Daniel and Knollmann, Till and Meyer auf der
Heide, Friedhelm}, year={2023}, pages={261–291} }'
chicago: 'Castenow, Jannik, Jonas Harbig, Daniel Jung, Till Knollmann, and Friedhelm
Meyer auf der Heide. “Gathering a Euclidean Closed Chain of Robots in Linear Time
and Improved Algorithms for Chain-Formation.” Theoretical Computer Science
939 (2023): 261–91. https://doi.org/10.1016/j.tcs.2022.10.031.'
ieee: 'J. Castenow, J. Harbig, D. Jung, T. Knollmann, and F. Meyer auf der Heide,
“Gathering a Euclidean Closed Chain of Robots in Linear Time and Improved Algorithms
for Chain-Formation,” Theoretical Computer Science, vol. 939, pp. 261–291,
2023, doi: 10.1016/j.tcs.2022.10.031.'
mla: Castenow, Jannik, et al. “Gathering a Euclidean Closed Chain of Robots in Linear
Time and Improved Algorithms for Chain-Formation.” Theoretical Computer Science,
vol. 939, Elsevier BV, 2023, pp. 261–91, doi:10.1016/j.tcs.2022.10.031.
short: J. Castenow, J. Harbig, D. Jung, T. Knollmann, F. Meyer auf der Heide, Theoretical
Computer Science 939 (2023) 261–291.
date_created: 2022-10-28T05:11:16Z
date_updated: 2023-01-30T09:20:09Z
department:
- _id: '63'
doi: 10.1016/j.tcs.2022.10.031
external_id:
arxiv:
- '2010.04424 '
intvolume: ' 939'
keyword:
- General Computer Science
- Theoretical Computer Science
language:
- iso: eng
page: 261-291
project:
- _id: '106'
name: 'Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme'
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier BV
status: public
title: Gathering a Euclidean Closed Chain of Robots in Linear Time and Improved Algorithms
for Chain-Formation
type: journal_article
user_id: '38705'
volume: 939
year: '2023'
...
---
_id: '34008'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Jonas
full_name: Harbig, Jonas
id: '47213'
last_name: Harbig
- first_name: Daniel
full_name: Jung, Daniel
id: '37827'
last_name: Jung
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Harbig J, Jung D, Kling P, Knollmann T, Meyer auf der Heide F.
A Unifying Approach to Efficient (Near-)Gathering of Disoriented Robots with Limited
Visibility . In: Hillel E, Palmieri R, Riviére E, eds. Proceedings of the 26th
International Conference on Principles of Distributed Systems (OPODIS) . Vol
253. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl
– Leibniz Zentrum für Informatik; 2023:15:1–15:25. doi:10.4230/LIPIcs.OPODIS.2022.15'
apa: Castenow, J., Harbig, J., Jung, D., Kling, P., Knollmann, T., & Meyer auf
der Heide, F. (2023). A Unifying Approach to Efficient (Near-)Gathering of Disoriented
Robots with Limited Visibility . In E. Hillel, R. Palmieri, & E. Riviére (Eds.),
Proceedings of the 26th International Conference on Principles of Distributed
Systems (OPODIS) (Vol. 253, p. 15:1–15:25). Schloss Dagstuhl – Leibniz Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2022.15
bibtex: '@inproceedings{Castenow_Harbig_Jung_Kling_Knollmann_Meyer auf der Heide_2023,
place={Brussels}, series={Leibniz International Proceedings in Informatics (LIPIcs)},
title={A Unifying Approach to Efficient (Near-)Gathering of Disoriented Robots
with Limited Visibility }, volume={253}, DOI={10.4230/LIPIcs.OPODIS.2022.15},
booktitle={Proceedings of the 26th International Conference on Principles of Distributed
Systems (OPODIS) }, publisher={Schloss Dagstuhl – Leibniz Zentrum für Informatik},
author={Castenow, Jannik and Harbig, Jonas and Jung, Daniel and Kling, Peter and
Knollmann, Till and Meyer auf der Heide, Friedhelm}, editor={Hillel, Eshcar and
Palmieri, Roberto and Riviére, Etienne}, year={2023}, pages={15:1–15:25}, collection={Leibniz
International Proceedings in Informatics (LIPIcs)} }'
chicago: 'Castenow, Jannik, Jonas Harbig, Daniel Jung, Peter Kling, Till Knollmann,
and Friedhelm Meyer auf der Heide. “A Unifying Approach to Efficient (Near-)Gathering
of Disoriented Robots with Limited Visibility .” In Proceedings of the 26th
International Conference on Principles of Distributed Systems (OPODIS) , edited
by Eshcar Hillel, Roberto Palmieri, and Etienne Riviére, 253:15:1–15:25. Leibniz
International Proceedings in Informatics (LIPIcs). Brussels: Schloss Dagstuhl
– Leibniz Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.OPODIS.2022.15.'
ieee: 'J. Castenow, J. Harbig, D. Jung, P. Kling, T. Knollmann, and F. Meyer auf
der Heide, “A Unifying Approach to Efficient (Near-)Gathering of Disoriented Robots
with Limited Visibility ,” in Proceedings of the 26th International Conference
on Principles of Distributed Systems (OPODIS) , Brussels, 2023, vol. 253,
p. 15:1–15:25, doi: 10.4230/LIPIcs.OPODIS.2022.15.'
mla: Castenow, Jannik, et al. “A Unifying Approach to Efficient (Near-)Gathering
of Disoriented Robots with Limited Visibility .” Proceedings of the 26th International
Conference on Principles of Distributed Systems (OPODIS) , edited by Eshcar
Hillel et al., vol. 253, Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2023,
p. 15:1–15:25, doi:10.4230/LIPIcs.OPODIS.2022.15.
short: 'J. Castenow, J. Harbig, D. Jung, P. Kling, T. Knollmann, F. Meyer auf der
Heide, in: E. Hillel, R. Palmieri, E. Riviére (Eds.), Proceedings of the 26th
International Conference on Principles of Distributed Systems (OPODIS) , Schloss
Dagstuhl – Leibniz Zentrum für Informatik, Brussels, 2023, p. 15:1–15:25.'
conference:
end_date: 2022-12-15
location: Brussels
name: 26th International Conference on Principles of Distributed Systems (OPODIS)
start_date: 2022-12-13
date_created: 2022-11-04T09:41:30Z
date_updated: 2023-02-15T14:53:12Z
department:
- _id: '63'
doi: 10.4230/LIPIcs.OPODIS.2022.15
editor:
- first_name: Eshcar
full_name: Hillel, Eshcar
last_name: Hillel
- first_name: Roberto
full_name: Palmieri, Roberto
last_name: Palmieri
- first_name: Etienne
full_name: Riviére, Etienne
last_name: Riviére
external_id:
arxiv:
- '2206.07567 '
intvolume: ' 253'
language:
- iso: eng
page: 15:1–15:25
place: Brussels
project:
- _id: '106'
name: 'Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme'
publication: 'Proceedings of the 26th International Conference on Principles of Distributed
Systems (OPODIS) '
publication_identifier:
isbn:
- 978-3-95977-265-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl – Leibniz Zentrum für Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: 'A Unifying Approach to Efficient (Near-)Gathering of Disoriented Robots with
Limited Visibility '
type: conference
user_id: '38705'
volume: 253
year: '2023'
...
---
_id: '45579'
author:
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
citation:
ama: Knollmann T. Online Algorithms for Allocating Heterogeneous Resources.;
2023. doi:10.17619/UNIPB/1-1751
apa: Knollmann, T. (2023). Online Algorithms for Allocating Heterogeneous Resources.
https://doi.org/10.17619/UNIPB/1-1751
bibtex: '@book{Knollmann_2023, title={Online Algorithms for Allocating Heterogeneous
Resources}, DOI={10.17619/UNIPB/1-1751},
author={Knollmann, Till}, year={2023} }'
chicago: Knollmann, Till. Online Algorithms for Allocating Heterogeneous Resources,
2023. https://doi.org/10.17619/UNIPB/1-1751.
ieee: T. Knollmann, Online Algorithms for Allocating Heterogeneous Resources.
2023.
mla: Knollmann, Till. Online Algorithms for Allocating Heterogeneous Resources.
2023, doi:10.17619/UNIPB/1-1751.
short: T. Knollmann, Online Algorithms for Allocating Heterogeneous Resources, 2023.
date_created: 2023-06-12T13:05:04Z
date_updated: 2023-06-12T21:03:14Z
department:
- _id: '63'
doi: 10.17619/UNIPB/1-1751
language:
- iso: eng
project:
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
grant_number: '160364472'
name: 'SFB 901 - A1: SFB 901 - Möglichkeiten und Grenzen lokaler Strategien in dynamischen
Netzen (Subproject A1)'
- _id: '1'
grant_number: '160364472'
name: 'SFB 901: SFB 901: On-The-Fly Computing - Individualisierte IT-Dienstleistungen
in dynamischen Märkten '
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Online Algorithms for Allocating Heterogeneous Resources
type: dissertation
user_id: '39241'
year: '2023'
...
---
_id: '45875'
author:
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
citation:
ama: 'Götte T, Knollmann T, Meyer auf der Heide F, Scheideler C, Werthmann J. Capabilities
and Limitations of Local Strategies in Dynamic Networks. In: Haake C-J, Meyer
auf der Heide F, Platzner M, Wachsmuth H, Wehrheim H, eds. On-The-Fly Computing
-- Individualized IT-Services in Dynamic Markets. Vol 412. Verlagsschriftenreihe
des Heinz Nixdorf Instituts. Heinz Nixdorf Institut, Universität Paderborn; 2023:1--20.
doi:10.5281/zenodo.8060372'
apa: Götte, T., Knollmann, T., Meyer auf der Heide, F., Scheideler, C., & Werthmann,
J. (2023). Capabilities and Limitations of Local Strategies in Dynamic Networks.
In C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, & H. Wehrheim
(Eds.), On-The-Fly Computing -- Individualized IT-services in dynamic markets
(Vol. 412, pp. 1--20). Heinz Nixdorf Institut, Universität Paderborn. https://doi.org/10.5281/zenodo.8060372
bibtex: '@inbook{Götte_Knollmann_Meyer auf der Heide_Scheideler_Werthmann_2023,
place={Paderborn}, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts},
title={Capabilities and Limitations of Local Strategies in Dynamic Networks},
volume={412}, DOI={10.5281/zenodo.8060372},
booktitle={On-The-Fly Computing -- Individualized IT-services in dynamic markets},
publisher={Heinz Nixdorf Institut, Universität Paderborn}, author={Götte, Thorsten
and Knollmann, Till and Meyer auf der Heide, Friedhelm and Scheideler, Christian
and Werthmann, Julian}, editor={Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm
and Platzner, Marco and Wachsmuth, Henning and Wehrheim, Heike}, year={2023},
pages={1--20}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts}
}'
chicago: 'Götte, Thorsten, Till Knollmann, Friedhelm Meyer auf der Heide, Christian
Scheideler, and Julian Werthmann. “Capabilities and Limitations of Local Strategies
in Dynamic Networks.” In On-The-Fly Computing -- Individualized IT-Services
in Dynamic Markets, edited by Claus-Jochen Haake, Friedhelm Meyer auf der
Heide, Marco Platzner, Henning Wachsmuth, and Heike Wehrheim, 412:1--20. Verlagsschriftenreihe
Des Heinz Nixdorf Instituts. Paderborn: Heinz Nixdorf Institut, Universität Paderborn,
2023. https://doi.org/10.5281/zenodo.8060372.'
ieee: 'T. Götte, T. Knollmann, F. Meyer auf der Heide, C. Scheideler, and J. Werthmann,
“Capabilities and Limitations of Local Strategies in Dynamic Networks,” in On-The-Fly
Computing -- Individualized IT-services in dynamic markets, vol. 412, C.-J.
Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, and H. Wehrheim, Eds.
Paderborn: Heinz Nixdorf Institut, Universität Paderborn, 2023, pp. 1--20.'
mla: Götte, Thorsten, et al. “Capabilities and Limitations of Local Strategies in
Dynamic Networks.” On-The-Fly Computing -- Individualized IT-Services in Dynamic
Markets, edited by Claus-Jochen Haake et al., vol. 412, Heinz Nixdorf Institut,
Universität Paderborn, 2023, pp. 1--20, doi:10.5281/zenodo.8060372.
short: 'T. Götte, T. Knollmann, F. Meyer auf der Heide, C. Scheideler, J. Werthmann,
in: C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, H. Wehrheim
(Eds.), On-The-Fly Computing -- Individualized IT-Services in Dynamic Markets,
Heinz Nixdorf Institut, Universität Paderborn, Paderborn, 2023, pp. 1--20.'
date_created: 2023-07-07T06:21:38Z
date_updated: 2023-07-07T06:21:57Z
ddc:
- '004'
department:
- _id: '7'
doi: 10.5281/zenodo.8060372
editor:
- first_name: Claus-Jochen
full_name: Haake, Claus-Jochen
last_name: Haake
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
last_name: Meyer auf der Heide
- first_name: Marco
full_name: Platzner, Marco
last_name: Platzner
- first_name: Henning
full_name: Wachsmuth, Henning
last_name: Wachsmuth
- first_name: Heike
full_name: Wehrheim, Heike
last_name: Wehrheim
file:
- access_level: open_access
content_type: application/pdf
creator: ups
date_created: 2023-07-07T06:20:43Z
date_updated: 2023-07-07T06:20:43Z
file_id: '45876'
file_name: A1-Chapter-SFB-Buch-Final.pdf
file_size: 543715
relation: main_file
file_date_updated: 2023-07-07T06:20:43Z
has_accepted_license: '1'
intvolume: ' 412'
language:
- iso: eng
oa: '1'
page: 1--20
place: Paderborn
project:
- _id: '1'
grant_number: '160364472'
name: 'SFB 901: SFB 901: On-The-Fly Computing - Individualisierte IT-Dienstleistungen
in dynamischen Märkten '
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
grant_number: '160364472'
name: 'SFB 901 - A1: SFB 901 - Möglichkeiten und Grenzen lokaler Strategien in dynamischen
Netzen (Subproject A1)'
publication: On-The-Fly Computing -- Individualized IT-services in dynamic markets
publisher: Heinz Nixdorf Institut, Universität Paderborn
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts
status: public
title: Capabilities and Limitations of Local Strategies in Dynamic Networks
type: book_chapter
user_id: '477'
volume: 412
year: '2023'
...
---
_id: '29843'
article_number: '104877'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Castenow J, Kling P, Knollmann T, Meyer auf der Heide F. A Discrete and Continuous
Study of the Max-Chain-Formation Problem. Information and Computation.
Published online 2022. doi:10.1016/j.ic.2022.104877
apa: Castenow, J., Kling, P., Knollmann, T., & Meyer auf der Heide, F. (2022).
A Discrete and Continuous Study of the Max-Chain-Formation Problem. Information
and Computation, Article 104877. https://doi.org/10.1016/j.ic.2022.104877
bibtex: '@article{Castenow_Kling_Knollmann_Meyer auf der Heide_2022, title={A Discrete
and Continuous Study of the Max-Chain-Formation Problem}, DOI={10.1016/j.ic.2022.104877},
number={104877}, journal={Information and Computation}, publisher={Elsevier BV},
author={Castenow, Jannik and Kling, Peter and Knollmann, Till and Meyer auf der
Heide, Friedhelm}, year={2022} }'
chicago: Castenow, Jannik, Peter Kling, Till Knollmann, and Friedhelm Meyer auf
der Heide. “A Discrete and Continuous Study of the Max-Chain-Formation Problem.”
Information and Computation, 2022. https://doi.org/10.1016/j.ic.2022.104877.
ieee: 'J. Castenow, P. Kling, T. Knollmann, and F. Meyer auf der Heide, “A Discrete
and Continuous Study of the Max-Chain-Formation Problem,” Information and Computation,
Art. no. 104877, 2022, doi: 10.1016/j.ic.2022.104877.'
mla: Castenow, Jannik, et al. “A Discrete and Continuous Study of the Max-Chain-Formation
Problem.” Information and Computation, 104877, Elsevier BV, 2022, doi:10.1016/j.ic.2022.104877.
short: J. Castenow, P. Kling, T. Knollmann, F. Meyer auf der Heide, Information
and Computation (2022).
date_created: 2022-02-15T07:38:28Z
date_updated: 2022-02-15T07:41:00Z
department:
- _id: '63'
doi: 10.1016/j.ic.2022.104877
keyword:
- Computational Theory and Mathematics
- Computer Science Applications
- Information Systems
- Theoretical Computer Science
language:
- iso: eng
project:
- _id: '106'
name: 'Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme'
publication: Information and Computation
publication_identifier:
issn:
- 0890-5401
publication_status: published
publisher: Elsevier BV
status: public
title: A Discrete and Continuous Study of the Max-Chain-Formation Problem
type: journal_article
user_id: '38705'
year: '2022'
...
---
_id: '31847'
abstract:
- lang: eng
text: "The famous $k$-Server Problem covers plenty of resource allocation scenarios,
and several variations have been studied extensively for decades. However, to
the best of our knowledge, no research has considered the problem if the servers
are not identical and requests can express which specific servers should serve
them. Therefore, we present a new model generalizing the $k$-Server Problem by
*preferences* of the requests and proceed to study it in a uniform metric space
for deterministic online algorithms (the special case of paging).\r\n\r\nIn our
model, requests can either demand to be answered by any server (*general requests*)
or by a specific one (*specific requests*). If only general requests appear, the
instance is one of the original $k$-Server Problem, and a lower bound for the
competitive ratio of $k$ applies. If only specific requests appear, a solution
with a competitive ratio of $1$ becomes trivial since there is no freedom regarding
the servers' movements. Perhaps counter-intuitively, we show that if both kinds
of requests appear, the lower bound raises to $2k-1$.\r\n\r\nWe study deterministic
online algorithms in uniform metrics and present two algorithms. The first one
has an adaptive competitive ratio dependent on the frequency of specific requests.
It achieves a worst-case competitive ratio of $3k-2$ while it is optimal when
only general or only specific requests appear (competitive ratio of $k$ and $1$,
respectively). The second has a fixed close-to-optimal worst-case competitive
ratio of $2k+14$. For the first algorithm, we show a lower bound of $3k-2$, while
the second algorithm has a lower bound of $2k-1$ when only general requests appear.\r\n
\ \r\nThe two algorithms differ in only one behavioral rule for each server
that significantly influences the competitive ratio. Each server acting according
to the rule allows approaching the worst-case lower bound, while it implies an
increased lower bound for $k$-Server instances. In other words, there is a trade-off
between performing well against instances of the $k$-Server Problem and instances
containing specific requests. We also show that no deterministic online algorithm
can be optimal for both kinds of instances simultaneously."
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Manuel
full_name: Malatyali, Manuel
id: '41265'
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. The
k-Server with Preferences Problem. In: Proceedings of the 34th ACM Symposium
on Parallelism in Algorithms and Architectures. Association for Computing
Machinery; 2022:345-356. doi:10.1145/3490148.3538595'
apa: Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der
Heide, F. (2022). The k-Server with Preferences Problem. Proceedings of the
34th ACM Symposium on Parallelism in Algorithms and Architectures, 345–356.
https://doi.org/10.1145/3490148.3538595
bibtex: '@inproceedings{Castenow_Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2022,
title={The k-Server with Preferences Problem}, DOI={10.1145/3490148.3538595},
booktitle={Proceedings of the 34th ACM Symposium on Parallelism in Algorithms
and Architectures}, publisher={Association for Computing Machinery}, author={Castenow,
Jannik and Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer
auf der Heide, Friedhelm}, year={2022}, pages={345–356} }'
chicago: Castenow, Jannik, Björn Feldkord, Till Knollmann, Manuel Malatyali, and
Friedhelm Meyer auf der Heide. “The K-Server with Preferences Problem.” In Proceedings
of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
345–56. Association for Computing Machinery, 2022. https://doi.org/10.1145/3490148.3538595.
ieee: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der
Heide, “The k-Server with Preferences Problem,” in Proceedings of the 34th
ACM Symposium on Parallelism in Algorithms and Architectures, 2022, pp. 345–356,
doi: 10.1145/3490148.3538595.'
mla: Castenow, Jannik, et al. “The K-Server with Preferences Problem.” Proceedings
of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2022, pp. 345–56, doi:10.1145/3490148.3538595.
short: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide,
in: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures,
Association for Computing Machinery, 2022, pp. 345–356.'
date_created: 2022-06-10T09:06:42Z
date_updated: 2022-08-02T08:07:30Z
department:
- _id: '63'
doi: 10.1145/3490148.3538595
external_id:
arxiv:
- '2205.11102'
keyword:
- K-Server Problem
- Heterogeneity
- Online Caching
language:
- iso: eng
page: 345-356
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
publication: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and
Architectures
publication_identifier:
isbn:
- '9781450391467'
publisher: Association for Computing Machinery
status: public
title: The k-Server with Preferences Problem
type: conference
user_id: '39241'
year: '2022'
...
---
_id: '31479'
author:
- first_name: Surender
full_name: Baswana, Surender
last_name: Baswana
- first_name: Shiv
full_name: Gupta, Shiv
last_name: Gupta
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
citation:
ama: Baswana S, Gupta S, Knollmann T. Mincut Sensitivity Data Structures for the
Insertion of an Edge. Algorithmica. Published online 2022. doi:10.1007/s00453-022-00978-0
apa: Baswana, S., Gupta, S., & Knollmann, T. (2022). Mincut Sensitivity Data
Structures for the Insertion of an Edge. Algorithmica. https://doi.org/10.1007/s00453-022-00978-0
bibtex: '@article{Baswana_Gupta_Knollmann_2022, title={Mincut Sensitivity Data Structures
for the Insertion of an Edge}, DOI={10.1007/s00453-022-00978-0},
journal={Algorithmica}, publisher={Springer Science and Business Media LLC}, author={Baswana,
Surender and Gupta, Shiv and Knollmann, Till}, year={2022} }'
chicago: Baswana, Surender, Shiv Gupta, and Till Knollmann. “Mincut Sensitivity
Data Structures for the Insertion of an Edge.” Algorithmica, 2022. https://doi.org/10.1007/s00453-022-00978-0.
ieee: 'S. Baswana, S. Gupta, and T. Knollmann, “Mincut Sensitivity Data Structures
for the Insertion of an Edge,” Algorithmica, 2022, doi: 10.1007/s00453-022-00978-0.'
mla: Baswana, Surender, et al. “Mincut Sensitivity Data Structures for the Insertion
of an Edge.” Algorithmica, Springer Science and Business Media LLC, 2022,
doi:10.1007/s00453-022-00978-0.
short: S. Baswana, S. Gupta, T. Knollmann, Algorithmica (2022).
date_created: 2022-05-27T10:09:24Z
date_updated: 2022-05-27T10:14:27Z
department:
- _id: '63'
doi: 10.1007/s00453-022-00978-0
genbank:
- tillk
keyword:
- Applied Mathematics
- Computer Science Applications
- General Computer Science
language:
- iso: eng
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
publication: Algorithmica
publication_identifier:
issn:
- 0178-4617
- 1432-0541
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Mincut Sensitivity Data Structures for the Insertion of an Edge
type: journal_article
user_id: '39241'
year: '2022'
...
---
_id: '21096'
abstract:
- lang: eng
text: While many research in distributed computing has covered solutions for self-stabilizing
computing and topologies, there is far less work on self-stabilization for distributed
data structures. However, when peers in peer-to-peer networks crash, a distributed
data structure may not remain intact. We present a self-stabilizing protocol for
a distributed data structure called the Hashed Patricia Trie (Kniesburges and
Scheideler WALCOM'11) that enables efficient prefix search on a set of keys. The
data structure has many applications while offering low overhead and efficient
operations when embedded on top of a Distributed Hash Table. Especially, longest
prefix matching for x can be done in O(log |x|) hash table read accesses. We show
how to maintain the structure in a self-stabilizing way, while assuring a low
overhead in a legal state and an asymptotically optimal memory demand of O(d)
bits, where d is the number of bits needed for storing all keys.
article_number: '104697'
author:
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: Knollmann T, Scheideler C. A self-stabilizing Hashed Patricia Trie. Information
and Computation. Published online 2022. doi:10.1016/j.ic.2021.104697
apa: Knollmann, T., & Scheideler, C. (2022). A self-stabilizing Hashed Patricia
Trie. Information and Computation, Article 104697. https://doi.org/10.1016/j.ic.2021.104697
bibtex: '@article{Knollmann_Scheideler_2022, title={A self-stabilizing Hashed Patricia
Trie}, DOI={10.1016/j.ic.2021.104697},
number={104697}, journal={Information and Computation}, author={Knollmann, Till
and Scheideler, Christian}, year={2022} }'
chicago: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia
Trie.” Information and Computation, 2022. https://doi.org/10.1016/j.ic.2021.104697.
ieee: 'T. Knollmann and C. Scheideler, “A self-stabilizing Hashed Patricia Trie,”
Information and Computation, Art. no. 104697, 2022, doi: 10.1016/j.ic.2021.104697.'
mla: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia
Trie.” Information and Computation, 104697, 2022, doi:10.1016/j.ic.2021.104697.
short: T. Knollmann, C. Scheideler, Information and Computation (2022).
date_created: 2021-01-29T09:39:40Z
date_updated: 2023-03-27T07:56:48Z
department:
- _id: '63'
- _id: '79'
doi: 10.1016/j.ic.2021.104697
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Information and Computation
publication_identifier:
issn:
- 0890-5401
publication_status: published
status: public
title: A self-stabilizing Hashed Patricia Trie
type: journal_article
user_id: '15504'
year: '2022'
...
---
_id: '23730'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Jonas
full_name: Harbig, Jonas
id: '47213'
last_name: Harbig
- first_name: Daniel
full_name: Jung, Daniel
id: '37827'
last_name: Jung
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Harbig J, Jung D, Knollmann T, Meyer auf der Heide F. Gathering
a Euclidean Closed Chain of Robots in Linear Time. In: Gasieniec L, Klasing R,
Radzik T, eds. Proceedings of the 17th International Symposium on Algorithms
and Experiments for Wireless Sensor Networks (ALGOSENSORS). Vol 12961. LNCS.
Springer; 2021:29-44. doi:10.1007/978-3-030-89240-1_3'
apa: Castenow, J., Harbig, J., Jung, D., Knollmann, T., & Meyer auf der Heide,
F. (2021). Gathering a Euclidean Closed Chain of Robots in Linear Time. In L.
Gasieniec, R. Klasing, & T. Radzik (Eds.), Proceedings of the 17th International
Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)
(Vol. 12961, pp. 29–44). Springer. https://doi.org/10.1007/978-3-030-89240-1_3
bibtex: '@inproceedings{Castenow_Harbig_Jung_Knollmann_Meyer auf der Heide_2021,
series={LNCS}, title={Gathering a Euclidean Closed Chain of Robots in Linear Time},
volume={12961}, DOI={10.1007/978-3-030-89240-1_3},
booktitle={Proceedings of the 17th International Symposium on Algorithms and Experiments
for Wireless Sensor Networks (ALGOSENSORS)}, publisher={Springer}, author={Castenow,
Jannik and Harbig, Jonas and Jung, Daniel and Knollmann, Till and Meyer auf der
Heide, Friedhelm}, editor={Gasieniec, Leszek and Klasing, Ralf and Radzik, Tomasz},
year={2021}, pages={29–44}, collection={LNCS} }'
chicago: Castenow, Jannik, Jonas Harbig, Daniel Jung, Till Knollmann, and Friedhelm
Meyer auf der Heide. “Gathering a Euclidean Closed Chain of Robots in Linear Time.”
In Proceedings of the 17th International Symposium on Algorithms and Experiments
for Wireless Sensor Networks (ALGOSENSORS), edited by Leszek Gasieniec, Ralf
Klasing, and Tomasz Radzik, 12961:29–44. LNCS. Springer, 2021. https://doi.org/10.1007/978-3-030-89240-1_3.
ieee: 'J. Castenow, J. Harbig, D. Jung, T. Knollmann, and F. Meyer auf der Heide,
“Gathering a Euclidean Closed Chain of Robots in Linear Time,” in Proceedings
of the 17th International Symposium on Algorithms and Experiments for Wireless
Sensor Networks (ALGOSENSORS), Lissabon, 2021, vol. 12961, pp. 29–44, doi:
10.1007/978-3-030-89240-1_3.'
mla: Castenow, Jannik, et al. “Gathering a Euclidean Closed Chain of Robots in Linear
Time.” Proceedings of the 17th International Symposium on Algorithms and Experiments
for Wireless Sensor Networks (ALGOSENSORS), edited by Leszek Gasieniec et
al., vol. 12961, Springer, 2021, pp. 29–44, doi:10.1007/978-3-030-89240-1_3.
short: 'J. Castenow, J. Harbig, D. Jung, T. Knollmann, F. Meyer auf der Heide, in:
L. Gasieniec, R. Klasing, T. Radzik (Eds.), Proceedings of the 17th International
Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS),
Springer, 2021, pp. 29–44.'
conference:
end_date: 2021-09-10
location: Lissabon
name: 17th International Symposium on Algorithms and Experiments for Wireless Sensor
Networks (ALGOSENSORS) 2021
start_date: 2021-09-09
date_created: 2021-09-03T09:01:25Z
date_updated: 2022-01-06T06:55:58Z
department:
- _id: '63'
doi: 10.1007/978-3-030-89240-1_3
editor:
- first_name: Leszek
full_name: Gasieniec, Leszek
last_name: Gasieniec
- first_name: Ralf
full_name: Klasing, Ralf
last_name: Klasing
- first_name: Tomasz
full_name: Radzik, Tomasz
last_name: Radzik
external_id:
arxiv:
- '2010.04424'
intvolume: ' 12961'
language:
- iso: eng
page: 29 - 44
project:
- _id: '106'
name: 'Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme'
publication: Proceedings of the 17th International Symposium on Algorithms and Experiments
for Wireless Sensor Networks (ALGOSENSORS)
publication_status: published
publisher: Springer
series_title: LNCS
status: public
title: Gathering a Euclidean Closed Chain of Robots in Linear Time
type: conference
user_id: '38705'
volume: 12961
year: '2021'
...
---
_id: '20683'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Manuel
full_name: Malatyali, Manuel
id: '41265'
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. Managing Multiple
Mobile Resources. Theory of Computing Systems. 2021;65:943–984. doi:10.1007/s00224-020-10023-8
apa: Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der Heide, F. (2021).
Managing Multiple Mobile Resources. Theory of Computing Systems, 65,
943–984. https://doi.org/10.1007/s00224-020-10023-8
bibtex: '@article{Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2021, title={Managing
Multiple Mobile Resources}, volume={65}, DOI={10.1007/s00224-020-10023-8},
journal={Theory of Computing Systems}, author={Feldkord, Björn and Knollmann,
Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2021}, pages={943–984}
}'
chicago: 'Feldkord, Björn, Till Knollmann, Manuel Malatyali, and Friedhelm Meyer
auf der Heide. “Managing Multiple Mobile Resources.” Theory of Computing Systems
65 (2021): 943–984. https://doi.org/10.1007/s00224-020-10023-8.'
ieee: 'B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der Heide, “Managing
Multiple Mobile Resources,” Theory of Computing Systems, vol. 65, pp. 943–984,
2021, doi: 10.1007/s00224-020-10023-8.'
mla: Feldkord, Björn, et al. “Managing Multiple Mobile Resources.” Theory of
Computing Systems, vol. 65, 2021, pp. 943–984, doi:10.1007/s00224-020-10023-8.
short: B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide, Theory of
Computing Systems 65 (2021) 943–984.
date_created: 2020-12-08T08:40:10Z
date_updated: 2022-01-06T06:54:31Z
department:
- _id: '63'
doi: 10.1007/s00224-020-10023-8
intvolume: ' 65'
language:
- iso: eng
page: 943–984
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Theory of Computing Systems
publication_status: published
status: public
title: Managing Multiple Mobile Resources
type: journal_article
user_id: '15415'
volume: 65
year: '2021'
...
---
_id: '26986'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Götte T, Knollmann T, Meyer auf der Heide F. The Max-Line-Formation
Problem – And New Insights for Gathering and Chain-Formation. In: Johnen C, Schiller
EM, Schmid S, eds. Proceedings of the 23rd International Symposium on Stabilization,
Safety, and Security of Distributed Systems, SSS 2021. Vol 13046. LNCS. Springer;
2021:289-304. doi:10.1007/978-3-030-91081-5_19'
apa: Castenow, J., Götte, T., Knollmann, T., & Meyer auf der Heide, F. (2021).
The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation.
In C. Johnen, E. M. Schiller, & S. Schmid (Eds.), Proceedings of the 23rd
International Symposium on Stabilization, Safety, and Security of Distributed
Systems, SSS 2021 (Vol. 13046, pp. 289–304). Springer. https://doi.org/10.1007/978-3-030-91081-5_19
bibtex: '@inproceedings{Castenow_Götte_Knollmann_Meyer auf der Heide_2021, series={LNCS},
title={The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation},
volume={13046}, DOI={10.1007/978-3-030-91081-5_19},
booktitle={Proceedings of the 23rd International Symposium on Stabilization, Safety,
and Security of Distributed Systems, SSS 2021}, publisher={Springer}, author={Castenow,
Jannik and Götte, Thorsten and Knollmann, Till and Meyer auf der Heide, Friedhelm},
editor={Johnen, C. and Schiller, E.M. and Schmid, S.}, year={2021}, pages={289–304},
collection={LNCS} }'
chicago: Castenow, Jannik, Thorsten Götte, Till Knollmann, and Friedhelm Meyer auf
der Heide. “The Max-Line-Formation Problem – And New Insights for Gathering and
Chain-Formation.” In Proceedings of the 23rd International Symposium on Stabilization,
Safety, and Security of Distributed Systems, SSS 2021, edited by C. Johnen,
E.M. Schiller, and S. Schmid, 13046:289–304. LNCS. Springer, 2021. https://doi.org/10.1007/978-3-030-91081-5_19.
ieee: 'J. Castenow, T. Götte, T. Knollmann, and F. Meyer auf der Heide, “The Max-Line-Formation
Problem – And New Insights for Gathering and Chain-Formation,” in Proceedings
of the 23rd International Symposium on Stabilization, Safety, and Security of
Distributed Systems, SSS 2021, Online, 2021, vol. 13046, pp. 289–304, doi:
10.1007/978-3-030-91081-5_19.'
mla: Castenow, Jannik, et al. “The Max-Line-Formation Problem – And New Insights
for Gathering and Chain-Formation.” Proceedings of the 23rd International Symposium
on Stabilization, Safety, and Security of Distributed Systems, SSS 2021, edited
by C. Johnen et al., vol. 13046, Springer, 2021, pp. 289–304, doi:10.1007/978-3-030-91081-5_19.
short: 'J. Castenow, T. Götte, T. Knollmann, F. Meyer auf der Heide, in: C. Johnen,
E.M. Schiller, S. Schmid (Eds.), Proceedings of the 23rd International Symposium
on Stabilization, Safety, and Security of Distributed Systems, SSS 2021, Springer,
2021, pp. 289–304.'
conference:
end_date: 2021-11-20
location: Online
name: 23rd International Symposium on Stabilization, Safety, and Security of Distributed
Systems
start_date: 2021-11-17
date_created: 2021-10-28T07:01:30Z
date_updated: 2022-01-07T15:24:10Z
department:
- _id: '63'
doi: 10.1007/978-3-030-91081-5_19
editor:
- first_name: C.
full_name: Johnen, C.
last_name: Johnen
- first_name: E.M.
full_name: Schiller, E.M.
last_name: Schiller
- first_name: S.
full_name: Schmid, S.
last_name: Schmid
external_id:
arxiv:
- '2109.11856'
intvolume: ' 13046'
language:
- iso: eng
page: '289-304 '
project:
- _id: '106'
name: 'Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme'
publication: Proceedings of the 23rd International Symposium on Stabilization, Safety,
and Security of Distributed Systems, SSS 2021
publication_status: published
publisher: Springer
series_title: LNCS
status: public
title: The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation
type: conference
user_id: '38705'
volume: 13046
year: '2021'
...
---
_id: '19899'
abstract:
- lang: eng
text: "Most existing robot formation problems seek a target formation of a certain\r\nminimal
and, thus, efficient structure. Examples include the Gathering\r\nand the Chain-Formation
problem. In this work, we study formation problems that\r\ntry to reach a maximal
structure, supporting for example an efficient\r\ncoverage in exploration scenarios.
A recent example is the NASA Shapeshifter\r\nproject, which describes how the
robots form a relay chain along which gathered\r\ndata from extraterrestrial cave
explorations may be sent to a home base.\r\n As a first step towards understanding
such maximization tasks, we introduce\r\nand study the Max-Chain-Formation problem,
where $n$ robots are ordered along a\r\nwinding, potentially self-intersecting
chain and must form a connected,\r\nstraight line of maximal length connecting
its two endpoints. We propose and\r\nanalyze strategies in a discrete and in a
continuous time model. In the\r\ndiscrete case, we give a complete analysis if
all robots are initially\r\ncollinear, showing that the worst-case time to reach
an\r\n$\\varepsilon$-approximation is upper bounded by $\\mathcal{O}(n^2 \\cdot
\\log\r\n(n/\\varepsilon))$ and lower bounded by $\\Omega(n^2 \\cdot~\\log\r\n(1/\\varepsilon))$.
If one endpoint of the chain remains stationary, this result\r\ncan be extended
to the non-collinear case. If both endpoints move, we identify\r\na family of
instances whose runtime is unbounded. For the continuous model, we\r\ngive a strategy
with an optimal runtime bound of $\\Theta(n)$. Avoiding an\r\nunbounded runtime
similar to the discrete case relies crucially on a\r\ncounter-intuitive aspect
of the strategy: slowing down the endpoints while all\r\nother robots move at
full speed. Surprisingly, we can show that a similar trick\r\ndoes not work in
the discrete model."
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Kling P, Knollmann T, Meyer auf der Heide F. A Discrete and Continuous
Study of the Max-Chain-Formation Problem – Slow Down to Speed Up. In: Devismes S,
Mittal N, eds. Stabilization, Safety, and Security of Distributed Systems -
22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020,
Proceedings. Vol 12514. Lecture Notes in Computer Science (LNCS). Springer;
2020:65-80. doi:10.1007/978-3-030-64348-5_6'
apa: Castenow, J., Kling, P., Knollmann, T., & Meyer auf der Heide, F. (2020).
A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down
to Speed Up. In S. Devismes & N. Mittal (Eds.), Stabilization, Safety,
and Security of Distributed Systems - 22nd International Symposium, SSS 2020,
Austin, Texas, USA, November 18-21, 2020, Proceedings (Vol. 12514, pp. 65–80).
Springer. https://doi.org/10.1007/978-3-030-64348-5_6
bibtex: '@inproceedings{Castenow_Kling_Knollmann_Meyer auf der Heide_2020, series={Lecture
Notes in Computer Science (LNCS)}, title={A Discrete and Continuous Study of the
Max-Chain-Formation Problem – Slow Down to Speed Up}, volume={12514}, DOI={10.1007/978-3-030-64348-5_6},
booktitle={Stabilization, Safety, and Security of Distributed Systems - 22nd International
Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings}, publisher={Springer},
author={Castenow, Jannik and Kling, Peter and Knollmann, Till and Meyer auf der
Heide, Friedhelm}, editor={Devismes , Stéphane and Mittal, Neeraj Editors}, year={2020},
pages={65–80}, collection={Lecture Notes in Computer Science (LNCS)} }'
chicago: Castenow, Jannik, Peter Kling, Till Knollmann, and Friedhelm Meyer auf
der Heide. “A Discrete and Continuous Study of the Max-Chain-Formation Problem
– Slow Down to Speed Up.” In Stabilization, Safety, and Security of Distributed
Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November
18-21, 2020, Proceedings, edited by Stéphane Devismes and Neeraj Mittal,
12514:65–80. Lecture Notes in Computer Science (LNCS). Springer, 2020. https://doi.org/10.1007/978-3-030-64348-5_6.
ieee: J. Castenow, P. Kling, T. Knollmann, and F. Meyer auf der Heide, “A Discrete
and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up,”
in Stabilization, Safety, and Security of Distributed Systems - 22nd International
Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings,
2020, vol. 12514, pp. 65–80.
mla: Castenow, Jannik, et al. “A Discrete and Continuous Study of the Max-Chain-Formation
Problem – Slow Down to Speed Up.” Stabilization, Safety, and Security of Distributed
Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November
18-21, 2020, Proceedings, edited by Stéphane Devismes and Neeraj Mittal,
vol. 12514, Springer, 2020, pp. 65–80, doi:10.1007/978-3-030-64348-5_6.
short: 'J. Castenow, P. Kling, T. Knollmann, F. Meyer auf der Heide, in: S. Devismes
, N. Mittal (Eds.), Stabilization, Safety, and Security of Distributed Systems
- 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21,
2020, Proceedings, Springer, 2020, pp. 65–80.'
date_created: 2020-10-06T07:27:10Z
date_updated: 2022-01-06T06:54:14Z
department:
- _id: '63'
doi: 10.1007/978-3-030-64348-5_6
editor:
- first_name: 'Stéphane '
full_name: 'Devismes , Stéphane '
last_name: 'Devismes '
- first_name: 'Neeraj '
full_name: 'Mittal, Neeraj '
last_name: Mittal
external_id:
arxiv:
- '2010.02043 '
intvolume: ' 12514'
language:
- iso: eng
page: 65-80
publication: Stabilization, Safety, and Security of Distributed Systems - 22nd International
Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings
publication_identifier:
isbn:
- 978-3-030-64347-8
publication_status: published
publisher: Springer
series_title: Lecture Notes in Computer Science (LNCS)
status: public
title: A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down
to Speed Up
type: conference
user_id: '38705'
volume: 12514
year: '2020'
...
---
_id: '20159'
abstract:
- lang: eng
text: "Let G = (V,E) be an undirected graph on n vertices with non-negative capacities
on its edges. The mincut sensitivity problem for the insertion of an edge is defined
as follows. Build a compact data structure for G and a given set S ⊆ V of vertices
that, on receiving any edge (x,y) ∈ S×S of positive capacity as query input, can
efficiently report the set of all pairs from S× S whose mincut value increases
upon insertion of the edge (x,y) to G. The only result that exists for this problem
is for a single pair of vertices (Picard and Queyranne, Mathematical Programming
Study, 13 (1980), 8-16). We present the following results for the single source
and the all-pairs versions of this problem. \r\n1) Single source: Given any designated
source vertex s, there exists a data structure of size \U0001D4AA(|S|) that can
output all those vertices from S whose mincut value to s increases upon insertion
of any given edge. The time taken by the data structure to answer any query is
\U0001D4AA(|S|). \r\n2) All-pairs: There exists an \U0001D4AA(|S|²) size data
structure that can output all those pairs of vertices from S× S whose mincut value
gets increased upon insertion of any given edge. The time taken by the data structure
to answer any query is \U0001D4AA(k), where k is the number of pairs of vertices
whose mincut increases. \r\nFor both these versions, we also address the problem
of reporting the values of the mincuts upon insertion of any given edge. To derive
our results, we use interesting insights into the nearest and the farthest mincuts
for a pair of vertices. In addition, a crucial result, that we establish and use
in our data structures, is that there exists a directed acyclic graph of \U0001D4AA(n)
size that compactly stores the farthest mincuts from all vertices of V to a designated
vertex s in the graph. We believe that this result is of independent interest,
especially, because it also complements a previously existing result by Hariharan
et al. (STOC 2007) that the nearest mincuts from all vertices of V to s is a laminar
family, and hence, can be stored compactly in a tree of \U0001D4AA(n) size."
author:
- first_name: Surender
full_name: Baswana, Surender
last_name: Baswana
- first_name: Shiv
full_name: Gupta, Shiv
last_name: Gupta
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
citation:
ama: 'Baswana S, Gupta S, Knollmann T. Mincut Sensitivity Data Structures for the
Insertion of an Edge. In: Grandoni F, Herman G, Sanders P, eds. 28th Annual
European Symposium on Algorithms (ESA 2020). Vol 173. Leibniz International
Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum
für Informatik; 2020:12:1-12:14. doi:10.4230/LIPIcs.ESA.2020.12'
apa: 'Baswana, S., Gupta, S., & Knollmann, T. (2020). Mincut Sensitivity Data
Structures for the Insertion of an Edge. In F. Grandoni, G. Herman, & P. Sanders
(Eds.), 28th Annual European Symposium on Algorithms (ESA 2020) (Vol. 173,
pp. 12:1-12:14). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2020.12'
bibtex: '@inproceedings{Baswana_Gupta_Knollmann_2020, place={Dagstuhl, Germany},
series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Mincut
Sensitivity Data Structures for the Insertion of an Edge}, volume={173}, DOI={10.4230/LIPIcs.ESA.2020.12},
booktitle={28th Annual European Symposium on Algorithms (ESA 2020)}, publisher={Schloss
Dagstuhl -- Leibniz-Zentrum für Informatik}, author={Baswana, Surender and Gupta,
Shiv and Knollmann, Till}, editor={Grandoni, Fabrizio and Herman, Grzegorz and
Sanders, PeterEditors}, year={2020}, pages={12:1-12:14}, collection={Leibniz International
Proceedings in Informatics (LIPIcs)} }'
chicago: 'Baswana, Surender, Shiv Gupta, and Till Knollmann. “Mincut Sensitivity
Data Structures for the Insertion of an Edge.” In 28th Annual European Symposium
on Algorithms (ESA 2020), edited by Fabrizio Grandoni, Grzegorz Herman, and
Peter Sanders, 173:12:1-12:14. Leibniz International Proceedings in Informatics
(LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik,
2020. https://doi.org/10.4230/LIPIcs.ESA.2020.12.'
ieee: S. Baswana, S. Gupta, and T. Knollmann, “Mincut Sensitivity Data Structures
for the Insertion of an Edge,” in 28th Annual European Symposium on Algorithms
(ESA 2020), 2020, vol. 173, pp. 12:1-12:14.
mla: Baswana, Surender, et al. “Mincut Sensitivity Data Structures for the Insertion
of an Edge.” 28th Annual European Symposium on Algorithms (ESA 2020), edited
by Fabrizio Grandoni et al., vol. 173, Schloss Dagstuhl -- Leibniz-Zentrum für
Informatik, 2020, pp. 12:1-12:14, doi:10.4230/LIPIcs.ESA.2020.12.
short: 'S. Baswana, S. Gupta, T. Knollmann, in: F. Grandoni, G. Herman, P. Sanders
(Eds.), 28th Annual European Symposium on Algorithms (ESA 2020), Schloss Dagstuhl
-- Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, pp. 12:1-12:14.'
date_created: 2020-10-21T12:00:20Z
date_updated: 2022-01-06T06:54:20Z
department:
- _id: '63'
doi: 10.4230/LIPIcs.ESA.2020.12
editor:
- first_name: Fabrizio
full_name: Grandoni, Fabrizio
last_name: Grandoni
- first_name: Grzegorz
full_name: Herman, Grzegorz
last_name: Herman
- first_name: Peter
full_name: Sanders, Peter
last_name: Sanders
intvolume: ' 173'
keyword:
- Mincut
- Sensitivity
- Data Structure
language:
- iso: eng
page: 12:1-12:14
place: Dagstuhl, Germany
publication: 28th Annual European Symposium on Algorithms (ESA 2020)
publication_identifier:
isbn:
- 978-3-95977-162-7
issn:
- 1868-8969
publisher: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Mincut Sensitivity Data Structures for the Insertion of an Edge
type: conference
user_id: '39241'
volume: 173
year: '2020'
...
---
_id: '20185'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Jonas
full_name: Harbig, Jonas
id: '47213'
last_name: Harbig
- first_name: Daniel
full_name: Jung, Daniel
id: '37827'
last_name: Jung
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Harbig J, Jung D, Knollmann T, Meyer auf der Heide F. Brief Announcement:
Gathering in Linear Time: A Closed Chain of Disoriented & Luminous Robots
with Limited Visibility . In: Devismes S, Mittal N, eds. Stabilization, Safety,
and Security of Distributed Systems - 22nd International Symposium, SSS 2020,
Austin, Texas, USA, November 18-21, 2020, Proceedings . Vol 12514. Lecture
Notes in Computer Science (LNCS). Springer; 2020:60-64. doi:10.1007/978-3-030-64348-5_5'
apa: 'Castenow, J., Harbig, J., Jung, D., Knollmann, T., & Meyer auf der Heide,
F. (2020). Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented
& Luminous Robots with Limited Visibility . In S. Devismes & N. Mittal
(Eds.), Stabilization, Safety, and Security of Distributed Systems - 22nd International
Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings
(Vol. 12514, pp. 60–64). Springer. https://doi.org/10.1007/978-3-030-64348-5_5'
bibtex: '@inproceedings{Castenow_Harbig_Jung_Knollmann_Meyer auf der Heide_2020,
series={Lecture Notes in Computer Science (LNCS)}, title={Brief Announcement:
Gathering in Linear Time: A Closed Chain of Disoriented & Luminous Robots
with Limited Visibility }, volume={12514}, DOI={10.1007/978-3-030-64348-5_5},
booktitle={Stabilization, Safety, and Security of Distributed Systems - 22nd International
Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings },
publisher={Springer}, author={Castenow, Jannik and Harbig, Jonas and Jung, Daniel
and Knollmann, Till and Meyer auf der Heide, Friedhelm}, editor={Devismes, Stéphane and Mittal,
NeerajEditors}, year={2020}, pages={60–64}, collection={Lecture Notes in Computer
Science (LNCS)} }'
chicago: 'Castenow, Jannik, Jonas Harbig, Daniel Jung, Till Knollmann, and Friedhelm
Meyer auf der Heide. “Brief Announcement: Gathering in Linear Time: A Closed Chain
of Disoriented & Luminous Robots with Limited Visibility .” In Stabilization,
Safety, and Security of Distributed Systems - 22nd International Symposium, SSS
2020, Austin, Texas, USA, November 18-21, 2020, Proceedings , edited by Stéphane Devismes
and Neeraj Mittal, 12514:60–64. Lecture Notes in Computer Science (LNCS). Springer,
2020. https://doi.org/10.1007/978-3-030-64348-5_5.'
ieee: 'J. Castenow, J. Harbig, D. Jung, T. Knollmann, and F. Meyer auf der Heide,
“Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented &
Luminous Robots with Limited Visibility ,” in Stabilization, Safety, and Security
of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas,
USA, November 18-21, 2020, Proceedings , 2020, vol. 12514, pp. 60–64.'
mla: 'Castenow, Jannik, et al. “Brief Announcement: Gathering in Linear Time: A
Closed Chain of Disoriented & Luminous Robots with Limited Visibility .” Stabilization,
Safety, and Security of Distributed Systems - 22nd International Symposium, SSS
2020, Austin, Texas, USA, November 18-21, 2020, Proceedings , edited by Stéphane Devismes
and Neeraj Mittal, vol. 12514, Springer, 2020, pp. 60–64, doi:10.1007/978-3-030-64348-5_5.'
short: 'J. Castenow, J. Harbig, D. Jung, T. Knollmann, F. Meyer auf der Heide, in:
S. Devismes, N. Mittal (Eds.), Stabilization, Safety, and Security of Distributed
Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November
18-21, 2020, Proceedings , Springer, 2020, pp. 60–64.'
date_created: 2020-10-23T08:50:28Z
date_updated: 2022-01-06T06:54:21Z
department:
- _id: '63'
doi: 10.1007/978-3-030-64348-5_5
editor:
- first_name: 'Stéphane '
full_name: 'Devismes, Stéphane '
last_name: Devismes
- first_name: Neeraj
full_name: ' Mittal, Neeraj'
last_name: ' Mittal'
external_id:
arxiv:
- '2010.04424 '
intvolume: ' 12514'
language:
- iso: eng
page: 60-64
publication: 'Stabilization, Safety, and Security of Distributed Systems - 22nd International
Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings '
publication_identifier:
isbn:
- 978-3-030-64347-8
publication_status: published
publisher: Springer
series_title: Lecture Notes in Computer Science (LNCS)
status: public
title: 'Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented
& Luminous Robots with Limited Visibility '
type: conference
user_id: '38705'
volume: 12514
year: '2020'
...
---
_id: '17370'
abstract:
- lang: eng
text: " We consider a natural extension to the metric uncapacitated Facility Location
Problem (FLP) in which requests ask for different commodities out of a finite
set \\( S \\) of commodities.\r\n Ravi and Sinha (SODA 2004) introduced the model
as the \\emph{Multi-Commodity Facility Location Problem} (MFLP) and considered
it an offline optimization problem.\r\n The model itself is similar to the FLP:
i.e., requests are located at points of a finite metric space and the task of
an algorithm is to construct facilities and assign requests to facilities while
minimizing the construction cost and the sum over all assignment distances.\r\n
\ In addition, requests and facilities are heterogeneous; they request or offer
multiple commodities out of $S$.\r\n A request has to be connected to a set of
facilities jointly offering the commodities demanded by it.\r\n In comparison
to the FLP, an algorithm has to decide not only if and where to place facilities,
but also which commodities to offer at each.\r\n\r\n To the best of our knowledge
we are the first to study the problem in its online variant in which requests,
their positions and their commodities are not known beforehand but revealed over
time.\r\n We present results regarding the competitive ratio.\r\n On the one
hand, we show that heterogeneity influences the competitive ratio by developing
a lower bound on the competitive ratio for any randomized online algorithm of
\\( \\Omega ( \\sqrt{|S|} + \\frac{\\log n}{\\log \\log n} ) \\) that already
holds for simple line metrics.\r\n Here, \\( n \\) is the number of requests.\r\n
\ On the other side, we establish a deterministic \\( \\mathcal{O}(\\sqrt{|S|}
\\cdot \\log n) \\)-competitive algorithm and a randomized \\( \\mathcal{O}(\\sqrt{|S|}
\\cdot \\frac{\\log n}{\\log \\log n} ) \\)-competitive algorithm.\r\n Further,
we show that when considering a more special class of cost functions for the construction
cost of a facility, the competitive ratio decreases given by our deterministic
algorithm depending on the function."
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- 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: 'Castenow J, Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. The
Online Multi-Commodity Facility Location Problem. In: Proceedings of the 32nd
ACM Symposium on Parallelism in Algorithms and Architectures. ; 2020. doi:10.1145/3350755.3400281'
apa: Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der
Heide, F. (2020). The Online Multi-Commodity Facility Location Problem. In Proceedings
of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures.
https://doi.org/10.1145/3350755.3400281
bibtex: '@inproceedings{Castenow_Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2020,
title={The Online Multi-Commodity Facility Location Problem}, DOI={10.1145/3350755.3400281},
booktitle={Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms
and Architectures}, author={Castenow, Jannik and Feldkord, Björn and Knollmann,
Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2020} }'
chicago: Castenow, Jannik, Björn Feldkord, Till Knollmann, Manuel Malatyali, and
Friedhelm Meyer auf der Heide. “The Online Multi-Commodity Facility Location Problem.”
In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
2020. https://doi.org/10.1145/3350755.3400281.
ieee: J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der
Heide, “The Online Multi-Commodity Facility Location Problem,” in Proceedings
of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
2020.
mla: Castenow, Jannik, et al. “The Online Multi-Commodity Facility Location Problem.”
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
2020, doi:10.1145/3350755.3400281.
short: 'J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide,
in: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
2020.'
date_created: 2020-07-14T07:53:20Z
date_updated: 2022-01-06T06:53:10Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1145/3350755.3400281
external_id:
arxiv:
- '2005.08391'
file:
- access_level: closed
content_type: application/pdf
creator: tillk
date_created: 2020-07-14T07:56:52Z
date_updated: 2020-07-14T07:56:52Z
file_id: '17373'
file_name: 3350755.3400281.pdf
file_size: 1271416
relation: main_file
success: 1
file_date_updated: 2020-07-14T07:56:52Z
has_accepted_license: '1'
keyword:
- Online Multi-Commodity Facility Location
- Competitive Ratio
- Online Optimization
- Facility Location Problem
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
Architectures
publication_identifier:
isbn:
- '9781450369350'
publication_status: published
status: public
title: The Online Multi-Commodity Facility Location Problem
type: conference
user_id: '39241'
year: '2020'
...
---
_id: '17371'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Kling P, Knollmann T, Meyer auf der Heide F. Brief Announcement:
A Discrete and Continuous Study of the Max-Chain-Formation Problem: Slow Down
to Speed up. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms
and Architectures. ; 2020. doi:10.1145/3350755.3400263'
apa: 'Castenow, J., Kling, P., Knollmann, T., & Meyer auf der Heide, F. (2020).
Brief Announcement: A Discrete and Continuous Study of the Max-Chain-Formation
Problem: Slow Down to Speed up. In Proceedings of the 32nd ACM Symposium on
Parallelism in Algorithms and Architectures. https://doi.org/10.1145/3350755.3400263'
bibtex: '@inproceedings{Castenow_Kling_Knollmann_Meyer auf der Heide_2020, title={Brief
Announcement: A Discrete and Continuous Study of the Max-Chain-Formation Problem:
Slow Down to Speed up}, DOI={10.1145/3350755.3400263},
booktitle={Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms
and Architectures}, author={Castenow, Jannik and Kling, Peter and Knollmann, Till
and Meyer auf der Heide, Friedhelm}, year={2020} }'
chicago: 'Castenow, Jannik, Peter Kling, Till Knollmann, and Friedhelm Meyer auf
der Heide. “Brief Announcement: A Discrete and Continuous Study of the Max-Chain-Formation
Problem: Slow Down to Speed Up.” In Proceedings of the 32nd ACM Symposium on
Parallelism in Algorithms and Architectures, 2020. https://doi.org/10.1145/3350755.3400263.'
ieee: 'J. Castenow, P. Kling, T. Knollmann, and F. Meyer auf der Heide, “Brief Announcement:
A Discrete and Continuous Study of the Max-Chain-Formation Problem: Slow Down
to Speed up,” in Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms
and Architectures, 2020.'
mla: 'Castenow, Jannik, et al. “Brief Announcement: A Discrete and Continuous Study
of the Max-Chain-Formation Problem: Slow Down to Speed Up.” Proceedings of
the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020,
doi:10.1145/3350755.3400263.'
short: 'J. Castenow, P. Kling, T. Knollmann, F. Meyer auf der Heide, in: Proceedings
of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020.'
date_created: 2020-07-14T07:53:47Z
date_updated: 2022-01-06T06:53:10Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1145/3350755.3400263
external_id:
arxiv:
- '2010.02043 '
file:
- access_level: closed
content_type: application/pdf
creator: janniksu
date_created: 2020-07-14T07:56:04Z
date_updated: 2020-07-14T07:56:04Z
file_id: '17372'
file_name: 3350755.3400263.pdf
file_size: 1078544
relation: main_file
success: 1
file_date_updated: 2020-07-14T07:56:04Z
has_accepted_license: '1'
language:
- iso: eng
publication: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
Architectures
publication_identifier:
isbn:
- '9781450369350'
publication_status: published
status: public
title: 'Brief Announcement: A Discrete and Continuous Study of the Max-Chain-Formation
Problem: Slow Down to Speed up'
type: conference
user_id: '38705'
year: '2020'
...
---
_id: '12870'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- 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: 'Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. Managing Multiple
Mobile Resources. In: Proceedings of the 17th Workshop on Approximation and
Online Algorithms (WAOA). Springer; 2019:120-137. doi:10.1007/978-3-030-39479-0_9'
apa: Feldkord, B., Knollmann, T., Malatyali, M., & Meyer auf der Heide, F. (2019).
Managing Multiple Mobile Resources. In Proceedings of the 17th Workshop on
Approximation and Online Algorithms (WAOA) (pp. 120–137). Springer. https://doi.org/10.1007/978-3-030-39479-0_9
bibtex: '@inproceedings{Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2019, title={Managing
Multiple Mobile Resources}, DOI={10.1007/978-3-030-39479-0_9},
booktitle={Proceedings of the 17th Workshop on Approximation and Online Algorithms
(WAOA)}, publisher={Springer}, author={Feldkord, Björn and Knollmann, Till and
Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2019}, pages={120–137}
}'
chicago: Feldkord, Björn, Till Knollmann, Manuel Malatyali, and Friedhelm Meyer
auf der Heide. “Managing Multiple Mobile Resources.” In Proceedings of the
17th Workshop on Approximation and Online Algorithms (WAOA), 120–37. Springer,
2019. https://doi.org/10.1007/978-3-030-39479-0_9.
ieee: B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der Heide, “Managing
Multiple Mobile Resources,” in Proceedings of the 17th Workshop on Approximation
and Online Algorithms (WAOA), 2019, pp. 120–137.
mla: Feldkord, Björn, et al. “Managing Multiple Mobile Resources.” Proceedings
of the 17th Workshop on Approximation and Online Algorithms (WAOA), Springer,
2019, pp. 120–37, doi:10.1007/978-3-030-39479-0_9.
short: 'B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide, in: Proceedings
of the 17th Workshop on Approximation and Online Algorithms (WAOA), Springer,
2019, pp. 120–137.'
date_created: 2019-07-22T09:00:05Z
date_updated: 2022-01-06T06:51:20Z
department:
- _id: '63'
doi: 10.1007/978-3-030-39479-0_9
external_id:
arxiv:
- '1907.09834'
language:
- iso: eng
page: 120 - 137
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Proceedings of the 17th Workshop on Approximation and Online Algorithms
(WAOA)
publication_status: published
publisher: Springer
status: public
title: Managing Multiple Mobile Resources
type: conference
user_id: '22704'
year: '2019'
...
---
_id: '4411'
abstract:
- lang: eng
text: "While a lot of research in distributed computing has covered solutions for
self-stabilizing computing and topologies, there is far less work on self-stabilization
for distributed data structures.\r\nConsidering crashing peers in peer-to-peer
networks, it should not be taken for granted that a distributed data structure
remains intact.\r\nIn this work, we present a self-stabilizing protocol for a
distributed data structure called the hashed Patricia Trie (Kniesburges and Scheideler
WALCOM'11) that enables efficient prefix search on a set of keys.\r\nThe data
structure has a wide area of applications including string matching problems while
offering low overhead and efficient operations when embedded on top of a distributed
hash table.\r\nEspecially, longest prefix matching for $x$ can be done in $\\mathcal{O}(\\log
|x|)$ hash table read accesses.\r\nWe show how to maintain the structure in a
self-stabilizing way.\r\nOur protocol assures low overhead in a legal state and
a total (asymptotically optimal) memory demand of $\\Theta(d)$ bits, where $d$
is the number of bits needed for storing all keys."
author:
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Knollmann T, Scheideler C. A Self-Stabilizing Hashed Patricia Trie. In: Izumi
T, Kuznetsov P, eds. Proceedings of the 20th International Symposium on Stabilization,
Safety, and Security of Distributed Systems (SSS). Vol 11201. Lecture Notes
of Computer Science. Springer, Cham; 2018. doi:10.1007/978-3-030-03232-6_1'
apa: 'Knollmann, T., & Scheideler, C. (2018). A Self-Stabilizing Hashed Patricia
Trie. In T. Izumi & P. Kuznetsov (Eds.), Proceedings of the 20th International
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
(Vol. 11201). Tokyo: Springer, Cham. https://doi.org/10.1007/978-3-030-03232-6_1'
bibtex: '@inproceedings{Knollmann_Scheideler_2018, series={Lecture Notes of Computer
Science}, title={A Self-Stabilizing Hashed Patricia Trie}, volume={11201}, DOI={10.1007/978-3-030-03232-6_1},
booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety,
and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Knollmann,
Till and Scheideler, Christian}, editor={Izumi, Taisuke and Kuznetsov, PetrEditors},
year={2018}, collection={Lecture Notes of Computer Science} }'
chicago: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia
Trie.” In Proceedings of the 20th International Symposium on Stabilization,
Safety, and Security of Distributed Systems (SSS), edited by Taisuke Izumi
and Petr Kuznetsov, Vol. 11201. Lecture Notes of Computer Science. Springer, Cham,
2018. https://doi.org/10.1007/978-3-030-03232-6_1.
ieee: T. Knollmann and C. Scheideler, “A Self-Stabilizing Hashed Patricia Trie,”
in Proceedings of the 20th International Symposium on Stabilization, Safety,
and Security of Distributed Systems (SSS), Tokyo, 2018, vol. 11201.
mla: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia
Trie.” Proceedings of the 20th International Symposium on Stabilization, Safety,
and Security of Distributed Systems (SSS), edited by Taisuke Izumi and Petr
Kuznetsov, vol. 11201, Springer, Cham, 2018, doi:10.1007/978-3-030-03232-6_1.
short: 'T. Knollmann, C. Scheideler, in: T. Izumi, P. Kuznetsov (Eds.), Proceedings
of the 20th International Symposium on Stabilization, Safety, and Security of
Distributed Systems (SSS), Springer, Cham, 2018.'
conference:
end_date: 2018-11-07
location: Tokyo
name: 20th International Symposium on Stabilization, Safety, and Security of Distributed
Systems (SSS)
start_date: 2018-11-04
date_created: 2018-09-17T13:12:18Z
date_updated: 2022-01-06T07:01:02Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
doi: 10.1007/978-3-030-03232-6_1
editor:
- first_name: Taisuke
full_name: Izumi, Taisuke
last_name: Izumi
- first_name: Petr
full_name: Kuznetsov, Petr
last_name: Kuznetsov
external_id:
arxiv:
- '1809.04923'
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T14:38:37Z
date_updated: 2018-11-02T14:38:37Z
file_id: '5277'
file_name: ASelf-stabilizingHashedPatrici.pdf
file_size: 500005
relation: main_file
success: 1
file_date_updated: 2018-11-02T14:38:37Z
has_accepted_license: '1'
intvolume: ' 11201'
keyword:
- Self-Stabilizing
- Prefix Search
- Distributed Data Structure
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Proceedings of the 20th International Symposium on Stabilization, Safety,
and Security of Distributed Systems (SSS)
publisher: Springer, Cham
series_title: Lecture Notes of Computer Science
status: public
title: A Self-Stabilizing Hashed Patricia Trie
type: conference
user_id: '39241'
volume: 11201
year: '2018'
...
---
_id: '4375'
abstract:
- lang: eng
text: "We present a peer-to-peer network that supports the efficient processing
of orthogonal range queries $R=\\bigtimes_{i=1}^{d}[a_i,\\,b_i]$ in a $d$-dimensional
point space.\\\\\r\nThe network is the same for each dimension, namely a distance
halving network like the one introduced by Naor and Wieder (ACM TALG'07).\r\nWe
show how to execute such range queries using $\\mathcal{O}\\left(2^{d'}d\\,\\log
m + d\\,|R|\\right)$ hops (and the same number of messages) in total. Here $[m]^d$
is the ground set, $|R|$ is the size and $d'$ the dimension of the queried range.\r\nFurthermore,
if the peers form a distributed network, the query can be answered in $\\mathcal{O}\\left(d\\,\\log
m + d\\,\\sum_{i=1}^{d}(b_i-a_i+1)\\right)$ communication rounds.\r\nOur algorithms
are based on a mapping of the Hilbert Curve through $[m]^d$ to the peers."
author:
- first_name: Markus
full_name: Benter, Markus
last_name: Benter
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Alexander
full_name: Setzer, Alexander
id: '11108'
last_name: Setzer
- first_name: Jannik
full_name: Sundermeier, Jannik
id: '38705'
last_name: Sundermeier
citation:
ama: 'Benter M, Knollmann T, Meyer auf der Heide F, Setzer A, Sundermeier J. A Peer-to-Peer
based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension.
In: Proceedings of the 4th International Symposium on Algorithmic Aspects of
Cloud Computing (ALGOCLOUD). ; 2018. doi:10.1007/978-3-030-19759-9_4'
apa: Benter, M., Knollmann, T., Meyer auf der Heide, F., Setzer, A., & Sundermeier,
J. (2018). A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
of arbitrary Dimension. In Proceedings of the 4th International Symposium on
Algorithmic Aspects of Cloud Computing (ALGOCLOUD). Helsinki. https://doi.org/10.1007/978-3-030-19759-9_4
bibtex: '@inproceedings{Benter_Knollmann_Meyer auf der Heide_Setzer_Sundermeier_2018,
title={A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
of arbitrary Dimension}, DOI={10.1007/978-3-030-19759-9_4},
booktitle={Proceedings of the 4th International Symposium on Algorithmic Aspects
of Cloud Computing (ALGOCLOUD)}, author={Benter, Markus and Knollmann, Till and
Meyer auf der Heide, Friedhelm and Setzer, Alexander and Sundermeier, Jannik},
year={2018} }'
chicago: Benter, Markus, Till Knollmann, Friedhelm Meyer auf der Heide, Alexander
Setzer, and Jannik Sundermeier. “A Peer-to-Peer Based Cloud Storage Supporting
Orthogonal Range Queries of Arbitrary Dimension.” In Proceedings of the 4th
International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD),
2018. https://doi.org/10.1007/978-3-030-19759-9_4.
ieee: M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, and J. Sundermeier,
“A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary
Dimension,” in Proceedings of the 4th International Symposium on Algorithmic
Aspects of Cloud Computing (ALGOCLOUD), Helsinki, 2018.
mla: Benter, Markus, et al. “A Peer-to-Peer Based Cloud Storage Supporting Orthogonal
Range Queries of Arbitrary Dimension.” Proceedings of the 4th International
Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD), 2018, doi:10.1007/978-3-030-19759-9_4.
short: 'M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, J. Sundermeier,
in: Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud
Computing (ALGOCLOUD), 2018.'
conference:
end_date: 2018-08-21
location: Helsinki
name: 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)
start_date: 2018-08-20
date_created: 2018-09-11T05:26:59Z
date_updated: 2022-01-06T07:01:00Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
doi: 10.1007/978-3-030-19759-9_4
file:
- access_level: closed
content_type: application/pdf
creator: tillk
date_created: 2018-11-27T10:03:33Z
date_updated: 2018-11-27T10:03:33Z
file_id: '5863'
file_name: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
of arbitrary Dimension.pdf
file_size: 1122875
relation: main_file
success: 1
file_date_updated: 2018-11-27T10:03:33Z
has_accepted_license: '1'
keyword:
- Distributed Storage
- Multi-Dimensional Range Queries
- Peer-to-Peer
- Hilbert Curve
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Proceedings of the 4th International Symposium on Algorithmic Aspects
of Cloud Computing (ALGOCLOUD)
status: public
title: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary
Dimension
type: conference
user_id: '14955'
year: '2018'
...
---
_id: '16461'
author:
- first_name: Pascal
full_name: Bemmann, Pascal
last_name: Bemmann
- first_name: Felix
full_name: Biermeier, Felix
last_name: Biermeier
- first_name: Jan
full_name: Bürmann, Jan
last_name: Bürmann
- first_name: Arne
full_name: Kemper, Arne
last_name: Kemper
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Steffen
full_name: Knorr, Steffen
last_name: Knorr
- first_name: Nils
full_name: Kothe, Nils
last_name: Kothe
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Manuel
full_name: Malatyali, Manuel
id: '41265'
last_name: Malatyali
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
- first_name: Johannes Sebastian
full_name: Schaefer, Johannes Sebastian
id: '30291'
last_name: Schaefer
- first_name: Jannik
full_name: Sundermeier, Jannik
id: '38705'
last_name: Sundermeier
citation:
ama: 'Bemmann P, Biermeier F, Bürmann J, et al. Monitoring of Domain-Related Problems
in Distributed Data Streams. In: Structural Information and Communication Complexity.
; 2017. doi:10.1007/978-3-319-72050-0_13'
apa: Bemmann, P., Biermeier, F., Bürmann, J., Kemper, A., Knollmann, T., Knorr,
S., Kothe, N., Mäcker, A., Malatyali, M., Meyer auf der Heide, F., Riechers, S.,
Schaefer, J. S., & Sundermeier, J. (2017). Monitoring of Domain-Related Problems
in Distributed Data Streams. In Structural Information and Communication Complexity.
https://doi.org/10.1007/978-3-319-72050-0_13
bibtex: '@inbook{Bemmann_Biermeier_Bürmann_Kemper_Knollmann_Knorr_Kothe_Mäcker_Malatyali_Meyer
auf der Heide_et al._2017, place={Cham}, title={Monitoring of Domain-Related Problems
in Distributed Data Streams}, DOI={10.1007/978-3-319-72050-0_13},
booktitle={Structural Information and Communication Complexity}, author={Bemmann,
Pascal and Biermeier, Felix and Bürmann, Jan and Kemper, Arne and Knollmann, Till
and Knorr, Steffen and Kothe, Nils and Mäcker, Alexander and Malatyali, Manuel
and Meyer auf der Heide, Friedhelm and et al.}, year={2017} }'
chicago: Bemmann, Pascal, Felix Biermeier, Jan Bürmann, Arne Kemper, Till Knollmann,
Steffen Knorr, Nils Kothe, et al. “Monitoring of Domain-Related Problems in Distributed
Data Streams.” In Structural Information and Communication Complexity.
Cham, 2017. https://doi.org/10.1007/978-3-319-72050-0_13.
ieee: P. Bemmann et al., “Monitoring of Domain-Related Problems in Distributed
Data Streams,” in Structural Information and Communication Complexity,
Cham, 2017.
mla: Bemmann, Pascal, et al. “Monitoring of Domain-Related Problems in Distributed
Data Streams.” Structural Information and Communication Complexity, 2017,
doi:10.1007/978-3-319-72050-0_13.
short: 'P. Bemmann, F. Biermeier, J. Bürmann, A. Kemper, T. Knollmann, S. Knorr,
N. Kothe, A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, J.S. Schaefer,
J. Sundermeier, in: Structural Information and Communication Complexity, Cham,
2017.'
date_created: 2020-04-08T07:20:20Z
date_updated: 2022-01-06T06:52:50Z
department:
- _id: '63'
doi: 10.1007/978-3-319-72050-0_13
external_id:
arxiv:
- 'arXiv:1706.03568 '
language:
- iso: eng
place: Cham
publication: Structural Information and Communication Complexity
publication_identifier:
isbn:
- '9783319720494'
- '9783319720500'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Monitoring of Domain-Related Problems in Distributed Data Streams
type: book_chapter
user_id: '15415'
year: '2017'
...