---
_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: '44769'
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: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Castenow J, Harbig J, Meyer auf der Heide F. Unifying Gathering Protocols
for Swarms of Mobile Robots. In: Lecture Notes in Computer Science. Springer
International Publishing; 2023. doi:10.1007/978-3-031-30448-4_1'
apa: Castenow, J., Harbig, J., & Meyer auf der Heide, F. (2023). Unifying Gathering
Protocols for Swarms of Mobile Robots. In Lecture Notes in Computer Science.
Springer International Publishing. https://doi.org/10.1007/978-3-031-30448-4_1
bibtex: '@inbook{Castenow_Harbig_Meyer auf der Heide_2023, place={Cham}, title={Unifying
Gathering Protocols for Swarms of Mobile Robots}, DOI={10.1007/978-3-031-30448-4_1},
booktitle={Lecture Notes in Computer Science}, publisher={Springer International
Publishing}, author={Castenow, Jannik and Harbig, Jonas and Meyer auf der Heide,
Friedhelm}, year={2023} }'
chicago: 'Castenow, Jannik, Jonas Harbig, and Friedhelm Meyer auf der Heide. “Unifying
Gathering Protocols for Swarms of Mobile Robots.” In Lecture Notes in Computer
Science. Cham: Springer International Publishing, 2023. https://doi.org/10.1007/978-3-031-30448-4_1.'
ieee: 'J. Castenow, J. Harbig, and F. Meyer auf der Heide, “Unifying Gathering Protocols
for Swarms of Mobile Robots,” in Lecture Notes in Computer Science, Cham:
Springer International Publishing, 2023.'
mla: Castenow, Jannik, et al. “Unifying Gathering Protocols for Swarms of Mobile
Robots.” Lecture Notes in Computer Science, Springer International Publishing,
2023, doi:10.1007/978-3-031-30448-4_1.
short: 'J. Castenow, J. Harbig, F. Meyer auf der Heide, in: Lecture Notes in Computer
Science, Springer International Publishing, Cham, 2023.'
date_created: 2023-05-11T13:13:45Z
date_updated: 2023-05-11T13:14:43Z
department:
- _id: '63'
doi: 10.1007/978-3-031-30448-4_1
language:
- iso: eng
place: Cham
project:
- _id: '106'
name: 'Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme'
publication: Lecture Notes in Computer Science
publication_identifier:
isbn:
- '9783031304477'
- '9783031304484'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer International Publishing
status: public
title: Unifying Gathering Protocols for Swarms of Mobile Robots
type: book_chapter
user_id: '38705'
year: '2023'
...
---
_id: '45580'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
citation:
ama: Castenow J. Local Protocols for Contracting and Expanding Robot Formation
Problems.; 2023. doi:10.17619/UNIPB/1-1750
apa: Castenow, J. (2023). Local Protocols for Contracting and Expanding Robot
Formation Problems. https://doi.org/10.17619/UNIPB/1-1750
bibtex: '@book{Castenow_2023, title={Local Protocols for Contracting and Expanding
Robot Formation Problems}, DOI={10.17619/UNIPB/1-1750},
author={Castenow, Jannik}, year={2023} }'
chicago: Castenow, Jannik. Local Protocols for Contracting and Expanding Robot
Formation Problems, 2023. https://doi.org/10.17619/UNIPB/1-1750.
ieee: J. Castenow, Local Protocols for Contracting and Expanding Robot Formation
Problems. 2023.
mla: Castenow, Jannik. Local Protocols for Contracting and Expanding Robot Formation
Problems. 2023, doi:10.17619/UNIPB/1-1750.
short: J. Castenow, Local Protocols for Contracting and Expanding Robot Formation
Problems, 2023.
date_created: 2023-06-12T13:06:58Z
date_updated: 2023-06-13T07:43:11Z
department:
- _id: '63'
doi: 10.17619/UNIPB/1-1750
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: Local Protocols for Contracting and Expanding Robot Formation Problems
type: dissertation
user_id: '38705'
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: '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: '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: '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: '16968'
abstract:
- lang: eng
text: "In this work, we initiate the research about the Gathering problem for robots\r\nwith
limited viewing range in the three-dimensional Euclidean space. In the\r\nGathering
problem, a set of initially scattered robots is required to gather at\r\nthe same
position. The robots' capabilities are very restricted -- they do not\r\nagree
on any coordinate system or compass, have a limited viewing range, have\r\nno
memory of the past and cannot communicate. We study the problem in two\r\ndifferent
time models, in FSYNC (fully synchronized discrete rounds) and the\r\ncontinuous
time model. For FSYNC, we introduce the 3D-Go-To-The-Center-strategy\r\nand prove
a runtime of $\\Theta(n^2)$ that matches the currently best runtime\r\nbound for
the same model in the Euclidean plane [SPAA'11]. Our main result is\r\nthe generalization
of contracting strategies (continuous time) from\r\n[Algosensors'17] to three
dimensions. In contracting strategies, every robot\r\nthat is located on the global
convex hull of all robots' positions moves with\r\nfull speed towards the inside
of the convex hull. We prove a runtime bound of\r\n$O(\\Delta \\cdot n^{3/2})$
for any three-dimensional contracting strategy, where\r\n$\\Delta$ denotes the
diameter of the initial configuration. This comes up to a\r\nfactor of $\\sqrt{n}$
close to the lower bound of $\\Omega (\\Delta \\cdot n)$\r\nwhich is already true
in two dimensions. In general, it might be hard for\r\nrobots with limited viewing
range to decide whether they are located on the\r\nglobal convex hull and which
movement maintains the connectivity of the swarm,\r\nrendering the design of concrete
contracting strategies a challenging task. We\r\nprove that the continuous variant
of 3D-Go-To-The-Center is contracting and\r\nkeeps the swarm connected. Moreover,
we give a simple design criterion for\r\nthree-dimensional contracting strategies
that maintains the connectivity of the\r\nswarm and introduce an exemplary strategy
based on this criterion."
- lang: eng
text: Best Student Paper Award
author:
- first_name: Michael
full_name: Braun, Michael
last_name: Braun
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Braun M, Castenow J, Meyer auf der Heide F. Local Gathering of Mobile Robots
in Three Dimensions. In: Proceedings of the 27th Conference on Structural Information
and Communication Complexity (SIROCCO). Springer; 2020. doi:10.1007/978-3-030-54921-3_4'
apa: 'Braun, M., Castenow, J., & Meyer auf der Heide, F. (2020). Local Gathering
of Mobile Robots in Three Dimensions. In Proceedings of the 27th Conference
on Structural Information and Communication Complexity (SIROCCO). Paderborn:
Springer. https://doi.org/10.1007/978-3-030-54921-3_4'
bibtex: '@inproceedings{Braun_Castenow_Meyer auf der Heide_2020, title={Local Gathering
of Mobile Robots in Three Dimensions}, DOI={10.1007/978-3-030-54921-3_4},
booktitle={Proceedings of the 27th Conference on Structural Information and Communication
Complexity (SIROCCO)}, publisher={Springer}, author={Braun, Michael and Castenow,
Jannik and Meyer auf der Heide, Friedhelm}, year={2020} }'
chicago: Braun, Michael, Jannik Castenow, and Friedhelm Meyer auf der Heide. “Local
Gathering of Mobile Robots in Three Dimensions.” In Proceedings of the 27th
Conference on Structural Information and Communication Complexity (SIROCCO).
Springer, 2020. https://doi.org/10.1007/978-3-030-54921-3_4.
ieee: M. Braun, J. Castenow, and F. Meyer auf der Heide, “Local Gathering of Mobile
Robots in Three Dimensions,” in Proceedings of the 27th Conference on Structural
Information and Communication Complexity (SIROCCO), Paderborn, 2020.
mla: Braun, Michael, et al. “Local Gathering of Mobile Robots in Three Dimensions.”
Proceedings of the 27th Conference on Structural Information and Communication
Complexity (SIROCCO), Springer, 2020, doi:10.1007/978-3-030-54921-3_4.
short: 'M. Braun, J. Castenow, F. Meyer auf der Heide, in: Proceedings of the 27th
Conference on Structural Information and Communication Complexity (SIROCCO), Springer,
2020.'
conference:
end_date: 2020-07-01
location: Paderborn
name: SIROCCO 2020
start_date: 2020-06-29
date_created: 2020-05-18T06:48:35Z
date_updated: 2022-01-06T06:53:00Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-030-54921-3_4
external_id:
arxiv:
- arXiv:2005.07495
file:
- access_level: closed
content_type: application/pdf
creator: janniksu
date_created: 2020-07-31T08:22:16Z
date_updated: 2020-07-31T08:22:16Z
file_id: '17504'
file_name: localGathering.pdf
file_size: 505712
relation: main_file
success: 1
file_date_updated: 2020-07-31T08:22:16Z
has_accepted_license: '1'
language:
- iso: eng
publication: Proceedings of the 27th Conference on Structural Information and Communication
Complexity (SIROCCO)
publisher: Springer
status: public
title: Local Gathering of Mobile Robots in Three Dimensions
type: conference
user_id: '38705'
year: '2020'
...
---
_id: '15169'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Christina
full_name: Kolb, Christina
id: '43647'
last_name: Kolb
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Castenow J, Kolb C, Scheideler C. A Bounding Box Overlay for Competitive Routing
in Hybrid Communication Networks. In: Proceedings of the 21st International
Conference on Distributed Computing and Networking (ICDCN). ACM.'
apa: 'Castenow, J., Kolb, C., & Scheideler, C. (n.d.). A Bounding Box Overlay
for Competitive Routing in Hybrid Communication Networks. In Proceedings of
the 21st International Conference on Distributed Computing and Networking (ICDCN).
Kolkata, Indien: ACM.'
bibtex: '@inproceedings{Castenow_Kolb_Scheideler, title={A Bounding Box Overlay
for Competitive Routing in Hybrid Communication Networks}, booktitle={Proceedings
of the 21st International Conference on Distributed Computing and Networking (ICDCN)},
publisher={ACM}, author={Castenow, Jannik and Kolb, Christina and Scheideler,
Christian} }'
chicago: Castenow, Jannik, Christina Kolb, and Christian Scheideler. “A Bounding
Box Overlay for Competitive Routing in Hybrid Communication Networks.” In Proceedings
of the 21st International Conference on Distributed Computing and Networking (ICDCN).
ACM, n.d.
ieee: J. Castenow, C. Kolb, and C. Scheideler, “A Bounding Box Overlay for Competitive
Routing in Hybrid Communication Networks,” in Proceedings of the 21st International
Conference on Distributed Computing and Networking (ICDCN), Kolkata, Indien.
mla: Castenow, Jannik, et al. “A Bounding Box Overlay for Competitive Routing in
Hybrid Communication Networks.” Proceedings of the 21st International Conference
on Distributed Computing and Networking (ICDCN), ACM.
short: 'J. Castenow, C. Kolb, C. Scheideler, in: Proceedings of the 21st International
Conference on Distributed Computing and Networking (ICDCN), ACM, n.d.'
conference:
end_date: 07.01.2020
location: Kolkata, Indien
name: '21st International Conference on Distributed Computing and Networking '
start_date: 04.01.2020
date_created: 2019-11-25T12:18:41Z
date_updated: 2022-01-06T06:52:16Z
department:
- _id: '63'
- _id: '79'
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 21st International Conference on Distributed Computing
and Networking (ICDCN)
publication_status: accepted
publisher: ACM
status: public
title: A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks
type: conference
user_id: '477'
year: '2020'
...
---
_id: '16299'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Jonas
full_name: Harbig, Jonas
last_name: Harbig
- first_name: Daniel
full_name: Jung, Daniel
id: '37827'
last_name: Jung
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Castenow J, Fischer M, Harbig J, Jung D, Meyer auf der Heide F. Gathering Anonymous,
Oblivious Robots on a Grid. Theoretical Computer Science. 2020;815:289-309.
doi:10.1016/j.tcs.2020.02.018
apa: Castenow, J., Fischer, M., Harbig, J., Jung, D., & Meyer auf der Heide,
F. (2020). Gathering Anonymous, Oblivious Robots on a Grid. Theoretical Computer
Science, 815, 289–309. https://doi.org/10.1016/j.tcs.2020.02.018
bibtex: '@article{Castenow_Fischer_Harbig_Jung_Meyer auf der Heide_2020, title={Gathering
Anonymous, Oblivious Robots on a Grid}, volume={815}, DOI={10.1016/j.tcs.2020.02.018},
journal={Theoretical Computer Science}, author={Castenow, Jannik and Fischer,
Matthias and Harbig, Jonas and Jung, Daniel and Meyer auf der Heide, Friedhelm},
year={2020}, pages={289–309} }'
chicago: 'Castenow, Jannik, Matthias Fischer, Jonas Harbig, Daniel Jung, and Friedhelm
Meyer auf der Heide. “Gathering Anonymous, Oblivious Robots on a Grid.” Theoretical
Computer Science 815 (2020): 289–309. https://doi.org/10.1016/j.tcs.2020.02.018.'
ieee: J. Castenow, M. Fischer, J. Harbig, D. Jung, and F. Meyer auf der Heide, “Gathering
Anonymous, Oblivious Robots on a Grid,” Theoretical Computer Science, vol.
815, pp. 289–309, 2020.
mla: Castenow, Jannik, et al. “Gathering Anonymous, Oblivious Robots on a Grid.”
Theoretical Computer Science, vol. 815, 2020, pp. 289–309, doi:10.1016/j.tcs.2020.02.018.
short: J. Castenow, M. Fischer, J. Harbig, D. Jung, F. Meyer auf der Heide, Theoretical
Computer Science 815 (2020) 289–309.
date_created: 2020-03-13T12:55:53Z
date_updated: 2022-01-06T06:52:48Z
department:
- _id: '63'
doi: 10.1016/j.tcs.2020.02.018
intvolume: ' 815'
language:
- iso: eng
page: 289-309
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
status: public
title: Gathering Anonymous, Oblivious Robots on a Grid
type: journal_article
user_id: '38705'
volume: 815
year: '2020'
...
---
_id: '14539'
author:
- first_name: Jannik
full_name: Castenow, Jannik
id: '38705'
last_name: Castenow
- first_name: Christina
full_name: Kolb, Christina
id: '43647'
last_name: Kolb
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Castenow J, Kolb C, Scheideler C. A Bounding Box Overlay for Competitive Routing
in Hybrid Communication Networks. In: Proceedings of the 26th International
Colloquium on Structural Information and Communication Complexity (SIROCCO).
; 2019:345-348. doi:10.1007/978-3-030-24922-9\_26'
apa: Castenow, J., Kolb, C., & Scheideler, C. (2019). A Bounding Box Overlay
for Competitive Routing in Hybrid Communication Networks. In Proceedings of
the 26th International Colloquium on Structural Information and Communication
Complexity (SIROCCO) (pp. 345–348). L’Aquila, Italy. https://doi.org/10.1007/978-3-030-24922-9\_26
bibtex: '@inproceedings{Castenow_Kolb_Scheideler_2019, title={A Bounding Box Overlay
for Competitive Routing in Hybrid Communication Networks}, DOI={10.1007/978-3-030-24922-9\_26},
booktitle={Proceedings of the 26th International Colloquium on Structural Information
and Communication Complexity (SIROCCO)}, author={Castenow, Jannik and Kolb, Christina
and Scheideler, Christian}, year={2019}, pages={345–348} }'
chicago: Castenow, Jannik, Christina Kolb, and Christian Scheideler. “A Bounding
Box Overlay for Competitive Routing in Hybrid Communication Networks.” In Proceedings
of the 26th International Colloquium on Structural Information and Communication
Complexity (SIROCCO), 345–48, 2019. https://doi.org/10.1007/978-3-030-24922-9\_26.
ieee: J. Castenow, C. Kolb, and C. Scheideler, “A Bounding Box Overlay for Competitive
Routing in Hybrid Communication Networks,” in Proceedings of the 26th International
Colloquium on Structural Information and Communication Complexity (SIROCCO),
L’Aquila, Italy, 2019, pp. 345–348.
mla: Castenow, Jannik, et al. “A Bounding Box Overlay for Competitive Routing in
Hybrid Communication Networks.” Proceedings of the 26th International Colloquium
on Structural Information and Communication Complexity (SIROCCO), 2019, pp.
345–48, doi:10.1007/978-3-030-24922-9\_26.
short: 'J. Castenow, C. Kolb, C. Scheideler, in: Proceedings of the 26th International
Colloquium on Structural Information and Communication Complexity (SIROCCO), 2019,
pp. 345–348.'
conference:
end_date: 2019-07-04
location: L'Aquila, Italy
name: SIROCCO 2019
start_date: 2019-07-01
date_created: 2019-11-04T10:09:35Z
date_updated: 2022-01-06T06:52:00Z
department:
- _id: '79'
- _id: '63'
doi: 10.1007/978-3-030-24922-9\_26
language:
- iso: eng
page: 345-348
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 26th International Colloquium on Structural Information
and Communication Complexity (SIROCCO)
status: public
title: A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks
type: conference
user_id: '477'
year: '2019'
...
---
_id: '4563'
abstract:
- lang: eng
text: "Routing is a challenging problem for wireless ad hoc networks, especially
when the nodes are mobile and spread so widely that in most cases multiple hops
are needed to route a message from one node to another. In fact, it is known that
any online routing protocol has a poor performance in the worst case, in a sense
that there is a distribution of nodes resulting in bad routing paths for that
protocol, even if the nodes know their geographic positions and the geographic
position of the destination of a message is known. The reason for that is that
radio holes in the ad hoc network may require messages to take long detours in
order to get to a destination, which are hard to find in an online fashion.\r\n\r\nIn
this paper, we assume that the wireless ad hoc network can make limited use of
long-range links provided by a global communication infrastructure like a cellular
infrastructure or a satellite in order to compute an abstraction of the wireless
ad hoc network that allows the messages to be sent along near-shortest paths in
the ad hoc network. We present distributed algorithms that compute an abstraction
of the ad hoc network in $\\mathcal{O}\\left(\\log ^2 n\\right)$ time using long-range
links, which results in $c$-competitive routing paths between any two nodes of
the ad hoc network for some constant $c$ if the convex hulls of the radio holes
do not intersect. We also show that the storage needed for the abstraction just
depends on the number and size of the radio holes in the wireless ad hoc network
and is independent on the total number of nodes, and this information just has
to be known to a few nodes for the routing to work.\r\n"
author:
- first_name: Daniel
full_name: Jung, Daniel
id: '37827'
last_name: Jung
- first_name: Christina
full_name: Kolb, Christina
id: '43647'
last_name: Kolb
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Jannik
full_name: Sundermeier, Jannik
id: '38705'
last_name: Sundermeier
citation:
ama: 'Jung D, Kolb C, Scheideler C, Sundermeier J. Competitive Routing in Hybrid
Communication Networks. In: Proceedings of the 14th International Symposium
on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) . Springer;
2018.'
apa: 'Jung, D., Kolb, C., Scheideler, C., & Sundermeier, J. (2018). Competitive
Routing in Hybrid Communication Networks. In Proceedings of the 14th International
Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) .
Helsinki: Springer.'
bibtex: '@inproceedings{Jung_Kolb_Scheideler_Sundermeier_2018, title={Competitive
Routing in Hybrid Communication Networks}, booktitle={Proceedings of the 14th
International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)
}, publisher={Springer}, author={Jung, Daniel and Kolb, Christina and Scheideler,
Christian and Sundermeier, Jannik}, year={2018} }'
chicago: Jung, Daniel, Christina Kolb, Christian Scheideler, and Jannik Sundermeier.
“Competitive Routing in Hybrid Communication Networks.” In Proceedings of the
14th International Symposium on Algorithms and Experiments for Wireless Networks
(ALGOSENSORS) . Springer, 2018.
ieee: D. Jung, C. Kolb, C. Scheideler, and J. Sundermeier, “Competitive Routing
in Hybrid Communication Networks,” in Proceedings of the 14th International
Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) ,
Helsinki, 2018.
mla: Jung, Daniel, et al. “Competitive Routing in Hybrid Communication Networks.”
Proceedings of the 14th International Symposium on Algorithms and Experiments
for Wireless Networks (ALGOSENSORS) , Springer, 2018.
short: 'D. Jung, C. Kolb, C. Scheideler, J. Sundermeier, in: Proceedings of the
14th International Symposium on Algorithms and Experiments for Wireless Networks
(ALGOSENSORS) , Springer, 2018.'
conference:
end_date: 2018-08-24
location: Helsinki
name: '14th International Symposium on Algorithms and Experiments for Wireless Networks
(ALGOSENSORS) '
start_date: 2018-08-23
date_created: 2018-10-02T07:06:05Z
date_updated: 2022-01-06T07:01:11Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2019-01-11T10:32:38Z
date_updated: 2019-01-11T10:32:38Z
file_id: '6621'
file_name: 23hybrid.pdf
file_size: 349034
relation: main_file
success: 1
file_date_updated: 2019-01-11T10:32:38Z
has_accepted_license: '1'
keyword:
- greedy routing
- ad hoc networks
- convex hulls
- c-competitiveness
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 14th International Symposium on Algorithms and Experiments
for Wireless Networks (ALGOSENSORS) '
publisher: Springer
status: public
title: Competitive Routing in Hybrid Communication Networks
type: conference
user_id: '38705'
year: '2018'
...
---
_id: '4565'
author:
- first_name: Daniel
full_name: Jung, Daniel
id: '37827'
last_name: Jung
- first_name: Christina
full_name: Kolb, Christina
id: '43647'
last_name: Kolb
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Jannik
full_name: Sundermeier, Jannik
id: '38705'
last_name: Sundermeier
citation:
ama: 'Jung D, Kolb C, Scheideler C, Sundermeier J. Brief Announcement: Competitive
Routing in Hybrid Communication Networks. In: Proceedings of the 30th on Symposium
on Parallelism in Algorithms and Architectures (SPAA). ACM Press; 2018. doi:10.1145/3210377.3210663'
apa: 'Jung, D., Kolb, C., Scheideler, C., & Sundermeier, J. (2018). Brief Announcement:
Competitive Routing in Hybrid Communication Networks. In Proceedings of the
30th on Symposium on Parallelism in Algorithms and Architectures (SPAA). Wien:
ACM Press. https://doi.org/10.1145/3210377.3210663'
bibtex: '@inproceedings{Jung_Kolb_Scheideler_Sundermeier_2018, title={Brief Announcement:
Competitive Routing in Hybrid Communication Networks}, DOI={10.1145/3210377.3210663},
booktitle={Proceedings of the 30th on Symposium on Parallelism in Algorithms and
Architectures (SPAA)}, publisher={ACM Press}, author={Jung, Daniel and Kolb, Christina
and Scheideler, Christian and Sundermeier, Jannik}, year={2018} }'
chicago: 'Jung, Daniel, Christina Kolb, Christian Scheideler, and Jannik Sundermeier.
“Brief Announcement: Competitive Routing in Hybrid Communication Networks.” In
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
(SPAA). ACM Press, 2018. https://doi.org/10.1145/3210377.3210663.'
ieee: 'D. Jung, C. Kolb, C. Scheideler, and J. Sundermeier, “Brief Announcement:
Competitive Routing in Hybrid Communication Networks,” in Proceedings of the
30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), Wien,
2018.'
mla: 'Jung, Daniel, et al. “Brief Announcement: Competitive Routing in Hybrid Communication
Networks.” Proceedings of the 30th on Symposium on Parallelism in Algorithms
and Architectures (SPAA), ACM Press, 2018, doi:10.1145/3210377.3210663.'
short: 'D. Jung, C. Kolb, C. Scheideler, J. Sundermeier, in: Proceedings of the
30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM Press,
2018.'
conference:
end_date: 2018-07-18
location: Wien
name: SPAA'18
start_date: 2018-07-17
date_created: 2018-10-02T07:34:47Z
date_updated: 2022-01-06T07:01:12Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
doi: 10.1145/3210377.3210663
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T13:48:10Z
date_updated: 2018-11-02T13:48:10Z
file_id: '5254'
file_name: p231-jung-1.pdf
file_size: 1025077
relation: main_file
success: 1
file_date_updated: 2018-11-02T13:48:10Z
has_accepted_license: '1'
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 30th on Symposium on Parallelism in Algorithms and
Architectures (SPAA)
publication_identifier:
isbn:
- '9781450357999'
publication_status: published
publisher: ACM Press
status: public
title: 'Brief Announcement: Competitive Routing in Hybrid Communication Networks'
type: conference
user_id: '38705'
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: '699'
author:
- first_name: Jannik
full_name: Sundermeier, Jannik
id: '38705'
last_name: Sundermeier
citation:
ama: Sundermeier J. Routing in Hybrid Communication Networks with Holes - Considering
Bounding Boxes as Hole Abstractions. Universität Paderborn; 2017.
apa: Sundermeier, J. (2017). Routing in Hybrid Communication Networks with Holes
- Considering Bounding Boxes as Hole Abstractions. Universität Paderborn.
bibtex: '@book{Sundermeier_2017, title={Routing in Hybrid Communication Networks
with Holes - Considering Bounding Boxes as Hole Abstractions}, publisher={Universität
Paderborn}, author={Sundermeier, Jannik}, year={2017} }'
chicago: Sundermeier, Jannik. Routing in Hybrid Communication Networks with Holes
- Considering Bounding Boxes as Hole Abstractions. Universität Paderborn,
2017.
ieee: J. Sundermeier, Routing in Hybrid Communication Networks with Holes - Considering
Bounding Boxes as Hole Abstractions. Universität Paderborn, 2017.
mla: Sundermeier, Jannik. Routing in Hybrid Communication Networks with Holes
- Considering Bounding Boxes as Hole Abstractions. Universität Paderborn,
2017.
short: J. Sundermeier, Routing in Hybrid Communication Networks with Holes - Considering
Bounding Boxes as Hole Abstractions, Universität Paderborn, 2017.
date_created: 2017-11-14T08:03:45Z
date_updated: 2022-01-06T07:03:25Z
department:
- _id: '79'
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: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
title: Routing in Hybrid Communication Networks with Holes - Considering Bounding
Boxes as Hole Abstractions
type: mastersthesis
user_id: '38705'
year: '2017'
...