---
_id: '43109'
author:
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Christina
full_name: Kolb, Christina
last_name: Kolb
- 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, Kolb C, Scheideler C, Werthmann J. Beep-and-Sleep: Message and Energy
Efficient Set Cover. Theor Comput Sci. 2023;950:113756. doi:10.1016/j.tcs.2023.113756'
apa: 'Götte, T., Kolb, C., Scheideler, C., & Werthmann, J. (2023). Beep-and-Sleep:
Message and Energy Efficient Set Cover. Theor. Comput. Sci., 950,
113756. https://doi.org/10.1016/j.tcs.2023.113756'
bibtex: '@article{Götte_Kolb_Scheideler_Werthmann_2023, title={Beep-and-Sleep: Message
and Energy Efficient Set Cover}, volume={950}, DOI={10.1016/j.tcs.2023.113756},
journal={Theor. Comput. Sci.}, author={Götte, Thorsten and Kolb, Christina and
Scheideler, Christian and Werthmann, Julian}, year={2023}, pages={113756} }'
chicago: 'Götte, Thorsten, Christina Kolb, Christian Scheideler, and Julian Werthmann.
“Beep-and-Sleep: Message and Energy Efficient Set Cover.” Theor. Comput. Sci.
950 (2023): 113756. https://doi.org/10.1016/j.tcs.2023.113756.'
ieee: 'T. Götte, C. Kolb, C. Scheideler, and J. Werthmann, “Beep-and-Sleep: Message
and Energy Efficient Set Cover,” Theor. Comput. Sci., vol. 950, p. 113756,
2023, doi: 10.1016/j.tcs.2023.113756.'
mla: 'Götte, Thorsten, et al. “Beep-and-Sleep: Message and Energy Efficient Set
Cover.” Theor. Comput. Sci., vol. 950, 2023, p. 113756, doi:10.1016/j.tcs.2023.113756.'
short: T. Götte, C. Kolb, C. Scheideler, J. Werthmann, Theor. Comput. Sci. 950 (2023)
113756.
date_created: 2023-03-27T07:45:44Z
date_updated: 2023-03-27T09:55:04Z
department:
- _id: '79'
doi: 10.1016/j.tcs.2023.113756
intvolume: ' 950'
language:
- iso: eng
page: '113756'
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: Theor. Comput. Sci.
status: public
title: 'Beep-and-Sleep: Message and Energy Efficient Set Cover'
type: journal_article
user_id: '15504'
volume: 950
year: '2023'
...
---
_id: '45188'
author:
- first_name: Julian
full_name: Werthmann, Julian
id: '50024'
last_name: Werthmann
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Sam
full_name: Coy, Sam
last_name: Coy
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Philipp
full_name: Schneider, Philipp
last_name: Schneider
citation:
ama: 'Werthmann J, Scheideler C, Coy S, Czumaj A, Schneider P. Routing Schemes for
Hybrid Communication Networks. In: ; 2023. doi:10.48550/ARXIV.2210.05333'
apa: Werthmann, J., Scheideler, C., Coy, S., Czumaj, A., & Schneider, P. (2023).
Routing Schemes for Hybrid Communication Networks. https://doi.org/10.48550/ARXIV.2210.05333
bibtex: '@inproceedings{Werthmann_Scheideler_Coy_Czumaj_Schneider_2023, title={Routing
Schemes for Hybrid Communication Networks}, DOI={10.48550/ARXIV.2210.05333},
author={Werthmann, Julian and Scheideler, Christian and Coy, Sam and Czumaj, Artur
and Schneider, Philipp}, year={2023} }'
chicago: Werthmann, Julian, Christian Scheideler, Sam Coy, Artur Czumaj, and Philipp
Schneider. “Routing Schemes for Hybrid Communication Networks,” 2023. https://doi.org/10.48550/ARXIV.2210.05333.
ieee: 'J. Werthmann, C. Scheideler, S. Coy, A. Czumaj, and P. Schneider, “Routing
Schemes for Hybrid Communication Networks,” 2023, doi: 10.48550/ARXIV.2210.05333.'
mla: Werthmann, Julian, et al. Routing Schemes for Hybrid Communication Networks.
2023, doi:10.48550/ARXIV.2210.05333.
short: 'J. Werthmann, C. Scheideler, S. Coy, A. Czumaj, P. Schneider, in: 2023.'
date_created: 2023-05-22T09:17:50Z
date_updated: 2023-05-22T09:37:25Z
department:
- _id: '79'
doi: 10.48550/ARXIV.2210.05333
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'
status: public
title: Routing Schemes for Hybrid Communication Networks
type: conference
user_id: '50024'
year: '2023'
...
---
_id: '45193'
author:
- first_name: Jinfeng
full_name: Dou, Jinfeng
id: '92888'
last_name: Dou
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Henning
full_name: Hillebrandt, Henning
last_name: Hillebrandt
- 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: 'Dou J, Götte T, Hillebrandt H, Scheideler C, Werthmann J. Brief Announcement:
Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs.
In: Proc. of the 42nd ACM Symposium on Principles of Distributed Computing
(PODC ’23). ; 2023.'
apa: 'Dou, J., Götte, T., Hillebrandt, H., Scheideler, C., & Werthmann, J. (2023).
Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes
for Planar Graphs. Proc. of the 42nd ACM Symposium on Principles of Distributed
Computing (PODC ’23). ACM Symposium on Principles of Distributed Computing
(PODC), Orlando, USA.'
bibtex: '@inproceedings{Dou_Götte_Hillebrandt_Scheideler_Werthmann_2023, title={Brief
Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes
for Planar Graphs}, booktitle={Proc. of the 42nd ACM Symposium on Principles of
Distributed Computing (PODC ’23)}, author={Dou, Jinfeng and Götte, Thorsten and
Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian}, year={2023}
}'
chicago: 'Dou, Jinfeng, Thorsten Götte, Henning Hillebrandt, Christian Scheideler,
and Julian Werthmann. “Brief Announcement: Distributed Construction of Near-Optimal
Compact Routing Schemes for Planar Graphs.” In Proc. of the 42nd ACM Symposium
on Principles of Distributed Computing (PODC ’23), 2023.'
ieee: 'J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, and J. Werthmann, “Brief
Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes
for Planar Graphs,” presented at the ACM Symposium on Principles of Distributed
Computing (PODC), Orlando, USA, 2023.'
mla: 'Dou, Jinfeng, et al. “Brief Announcement: Distributed Construction of Near-Optimal
Compact Routing Schemes for Planar Graphs.” Proc. of the 42nd ACM Symposium
on Principles of Distributed Computing (PODC ’23), 2023.'
short: 'J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, J. Werthmann, in: Proc.
of the 42nd ACM Symposium on Principles of Distributed Computing (PODC ’23), 2023.'
conference:
end_date: 2023-06-25
location: Orlando, USA
name: ACM Symposium on Principles of Distributed Computing (PODC)
start_date: 2023-06-19
date_created: 2023-05-22T14:42:31Z
date_updated: 2023-05-22T16:04:56Z
language:
- iso: eng
project:
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
- _id: '1'
name: 'SFB 901: SFB 901'
publication: Proc. of the 42nd ACM Symposium on Principles of Distributed Computing
(PODC '23)
status: public
title: 'Brief Announcement: Distributed Construction of Near-Optimal Compact Routing
Schemes for Planar Graphs'
type: conference
user_id: '34727'
year: '2023'
...
---
_id: '45192'
author:
- first_name: Thorsten
full_name: Götte, Thorsten
id: '34727'
last_name: Götte
- first_name: Kristian
full_name: Hinnenthal, Kristian
id: '32229'
last_name: Hinnenthal
- 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, Hinnenthal K, Scheideler C, Werthmann J. Time-Optimal Construction
of Overlays. Distributed Computing. Published online 2023. doi:https://doi.org/10.1007/s00446-023-00442-4
apa: Götte, T., Hinnenthal, K., Scheideler, C., & Werthmann, J. (2023). Time-Optimal
Construction of Overlays. Distributed Computing. https://doi.org/10.1007/s00446-023-00442-4
bibtex: '@article{Götte_Hinnenthal_Scheideler_Werthmann_2023, title={Time-Optimal
Construction of Overlays}, DOI={https://doi.org/10.1007/s00446-023-00442-4},
journal={Distributed Computing}, author={Götte, Thorsten and Hinnenthal, Kristian
and Scheideler, Christian and Werthmann, Julian}, year={2023} }'
chicago: Götte, Thorsten, Kristian Hinnenthal, Christian Scheideler, and Julian
Werthmann. “Time-Optimal Construction of Overlays.” Distributed Computing,
2023. https://doi.org/10.1007/s00446-023-00442-4.
ieee: 'T. Götte, K. Hinnenthal, C. Scheideler, and J. Werthmann, “Time-Optimal Construction
of Overlays,” Distributed Computing, 2023, doi: https://doi.org/10.1007/s00446-023-00442-4.'
mla: Götte, Thorsten, et al. “Time-Optimal Construction of Overlays.” Distributed
Computing, 2023, doi:https://doi.org/10.1007/s00446-023-00442-4.
short: T. Götte, K. Hinnenthal, C. Scheideler, J. Werthmann, Distributed Computing
(2023).
date_created: 2023-05-22T14:34:34Z
date_updated: 2023-05-23T12:38:57Z
doi: https://doi.org/10.1007/s00446-023-00442-4
language:
- iso: eng
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
- _id: '13'
name: 'SFB 901 - C1: SFB 901 - Subproject C1'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
publication: Distributed Computing
status: public
title: Time-Optimal Construction of Overlays
type: journal_article
user_id: '477'
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: '45863'
abstract:
- lang: eng
text: "In the proposal for our CRC in 2011, we formulated a vision of markets for\r\nIT
services that describes an approach to the provision of such services\r\nthat
was novel at that time and, to a large extent, remains so today:\r\n„Our vision
of on-the-fly computing is that of IT services individually and\r\nautomatically
configured and brought to execution from flexibly combinable\r\nservices traded
on markets. At the same time, we aim at organizing\r\nmarkets whose participants
maintain a lively market of services through\r\nappropriate entrepreneurial actions.“\r\nOver
the last 12 years, we have developed methods and techniques to\r\naddress problems
critical to the convenient, efficient, and secure use of\r\non-the-fly computing.
Among other things, we have made the description\r\nof services more convenient
by allowing natural language input,\r\nincreased the quality of configured services
through (natural language)\r\ninteraction and more efficient configuration processes
and analysis\r\nprocedures, made the quality of (the products of) providers in
the\r\nmarketplace transparent through reputation systems, and increased the\r\nresource
efficiency of execution through reconfigurable heterogeneous\r\ncomputing nodes
and an integrated treatment of service description and\r\nconfiguration. We have
also developed network infrastructures that have\r\na high degree of adaptivity,
scalability, efficiency, and reliability, and\r\nprovide cryptographic guarantees
of anonymity and security for market\r\nparticipants and their products and services.\r\nTo
demonstrate the pervasiveness of the OTF computing approach, we\r\nhave implemented
a proof-of-concept for OTF computing that can run\r\ntypical scenarios of an OTF
market. We illustrated the approach using\r\na cutting-edge application scenario
– automated machine learning (AutoML).\r\nFinally, we have been pushing our work
for the perpetuation of\r\nOn-The-Fly Computing beyond the SFB and sharing the
expertise gained\r\nin the SFB in events with industry partners as well as transfer
projects.\r\nThis work required a broad spectrum of expertise. Computer scientists\r\nand
economists with research interests such as computer networks and\r\ndistributed
algorithms, security and cryptography, software engineering\r\nand verification,
configuration and machine learning, computer engineering\r\nand HPC, microeconomics
and game theory, business informatics\r\nand management have successfully collaborated
here."
alternative_title:
- Collaborative Research Centre 901 (2011 – 2023)
author:
- first_name: Claus-Jochen
full_name: Haake, Claus-Jochen
id: '20801'
last_name: Haake
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Marco
full_name: Platzner, Marco
id: '398'
last_name: Platzner
- first_name: Henning
full_name: Wachsmuth, Henning
id: '3900'
last_name: Wachsmuth
- first_name: Heike
full_name: Wehrheim, Heike
id: '573'
last_name: Wehrheim
citation:
ama: Haake C-J, Meyer auf der Heide F, Platzner M, Wachsmuth H, Wehrheim H. On-The-Fly
Computing -- Individualized IT-Services in Dynamic Markets. Vol 412. Heinz
Nixdorf Institut, Universität Paderborn; 2023. doi:10.17619/UNIPB/1-1797
apa: Haake, C.-J., Meyer auf der Heide, F., Platzner, M., Wachsmuth, H., & Wehrheim,
H. (2023). On-The-Fly Computing -- Individualized IT-services in dynamic markets
(Vol. 412). Heinz Nixdorf Institut, Universität Paderborn. https://doi.org/10.17619/UNIPB/1-1797
bibtex: '@book{Haake_Meyer auf der Heide_Platzner_Wachsmuth_Wehrheim_2023, place={Paderborn},
series={Verlagsschriftenreihe des Heinz Nixdorf Instituts}, title={On-The-Fly
Computing -- Individualized IT-services in dynamic markets}, volume={412}, DOI={10.17619/UNIPB/1-1797}, publisher={Heinz
Nixdorf Institut, Universität Paderborn}, author={Haake, Claus-Jochen and Meyer
auf der Heide, Friedhelm and Platzner, Marco and Wachsmuth, Henning and Wehrheim,
Heike}, year={2023}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts}
}'
chicago: 'Haake, Claus-Jochen, Friedhelm Meyer auf der Heide, Marco Platzner, Henning
Wachsmuth, and Heike Wehrheim. On-The-Fly Computing -- Individualized IT-Services
in Dynamic Markets. Vol. 412. Verlagsschriftenreihe Des Heinz Nixdorf Instituts.
Paderborn: Heinz Nixdorf Institut, Universität Paderborn, 2023. https://doi.org/10.17619/UNIPB/1-1797.'
ieee: 'C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, and H. Wehrheim,
On-The-Fly Computing -- Individualized IT-services in dynamic markets,
vol. 412. Paderborn: Heinz Nixdorf Institut, Universität Paderborn, 2023.'
mla: Haake, Claus-Jochen, et al. On-The-Fly Computing -- Individualized IT-Services
in Dynamic Markets. Heinz Nixdorf Institut, Universität Paderborn, 2023, doi:10.17619/UNIPB/1-1797.
short: C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, H. Wehrheim,
On-The-Fly Computing -- Individualized IT-Services in Dynamic Markets, Heinz Nixdorf
Institut, Universität Paderborn, Paderborn, 2023.
date_created: 2023-07-05T07:16:51Z
date_updated: 2023-08-29T06:44:36Z
ddc:
- '000'
department:
- _id: '7'
doi: 10.17619/UNIPB/1-1797
file:
- access_level: open_access
content_type: application/pdf
creator: ups
date_created: 2023-07-05T07:15:55Z
date_updated: 2023-07-05T07:19:14Z
file_id: '45864'
file_name: SFB-Buch-Final.pdf
file_size: 15480050
relation: main_file
file_date_updated: 2023-07-05T07:19:14Z
has_accepted_license: '1'
intvolume: ' 412'
language:
- iso: eng
oa: '1'
page: '247'
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: '3'
name: 'SFB 901 - B: SFB 901 - Project Area B'
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
- _id: '82'
name: 'SFB 901 - T: SFB 901 - Project Area T'
- _id: '5'
grant_number: '160364472'
name: 'SFB 901 - A1: SFB 901 - Möglichkeiten und Grenzen lokaler Strategien in dynamischen
Netzen (Subproject A1)'
- _id: '7'
grant_number: '160364472'
name: 'SFB 901 - A3: SFB 901 - Der Markt für Services: Anreize, Algorithmen, Implementation
(Subproject A3)'
- _id: '8'
grant_number: '160364472'
name: 'SFB 901 - A4: SFB 901 - Empirische Analysen in Märkten für OTF Dienstleistungen
(Subproject A4)'
- _id: '9'
grant_number: '160364472'
name: 'SFB 901 - B1: SFB 901 - Parametrisierte Servicespezifikation (Subproject
B1)'
- _id: '10'
grant_number: '160364472'
name: 'SFB 901 - B2: Konfiguration und Bewertung (B02)'
- _id: '11'
name: 'SFB 901 - B3: SFB 901 - Subproject B3'
- _id: '12'
name: 'SFB 901 - B4: SFB 901 - Subproject B4'
- _id: '13'
name: 'SFB 901 - C1: SFB 901 - Subproject C1'
- _id: '14'
grant_number: '160364472'
name: 'SFB 901 - C2: SFB 901 - On-The-Fly Compute Centers I: Heterogene Ausführungsumgebungen
(Subproject C2)'
- _id: '16'
grant_number: '160364472'
name: 'SFB 901 - C4: SFB 901 - On-The-Fly Compute Centers II: Ausführung komponierter
Dienste in konfigurierbaren Rechenzentren (Subproject C4)'
- _id: '17'
name: 'SFB 901 - C5: SFB 901 - Subproject C5'
- _id: '83'
name: 'SFB 901 - T1: SFB 901 -Subproject T1'
- _id: '84'
name: 'SFB 901 - T2: SFB 901 -Subproject T2'
publication_identifier:
unknown:
- 978-3-947647-31-6
publisher: Heinz Nixdorf Institut, Universität Paderborn
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts
status: public
title: On-The-Fly Computing -- Individualized IT-services in dynamic markets
type: book
user_id: '477'
volume: 412
year: '2023'
...
---
_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: '32602'
author:
- first_name: Andreas
full_name: Padalkin, Andreas
id: '88238'
last_name: Padalkin
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Daniel
full_name: Warner, Daniel
id: '3902'
last_name: Warner
citation:
ama: 'Padalkin A, Scheideler C, Warner D. The Structural Power of Reconfigurable
Circuits in the Amoebot Model. In: Ouldridge TE, Wickham SFJ, eds. 28th International
Conference on DNA Computing and Molecular Programming (DNA 28). Vol 238. Leibniz
International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum
für Informatik; 2022:8:1–8:22. doi:10.4230/LIPIcs.DNA.28.8'
apa: Padalkin, A., Scheideler, C., & Warner, D. (2022). The Structural Power
of Reconfigurable Circuits in the Amoebot Model. In T. E. Ouldridge & S. F.
J. Wickham (Eds.), 28th International Conference on DNA Computing and Molecular
Programming (DNA 28) (Vol. 238, p. 8:1–8:22). Schloss Dagstuhl – Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.DNA.28.8
bibtex: '@inproceedings{Padalkin_Scheideler_Warner_2022, place={Dagstuhl, Germany},
series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={The
Structural Power of Reconfigurable Circuits in the Amoebot Model}, volume={238},
DOI={10.4230/LIPIcs.DNA.28.8},
booktitle={28th International Conference on DNA Computing and Molecular Programming
(DNA 28)}, publisher={Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, author={Padalkin,
Andreas and Scheideler, Christian and Warner, Daniel}, editor={Ouldridge, Thomas
E. and Wickham, Shelley F. J.}, year={2022}, pages={8:1–8:22}, collection={Leibniz
International Proceedings in Informatics (LIPIcs)} }'
chicago: 'Padalkin, Andreas, Christian Scheideler, and Daniel Warner. “The Structural
Power of Reconfigurable Circuits in the Amoebot Model.” In 28th International
Conference on DNA Computing and Molecular Programming (DNA 28), edited by
Thomas E. Ouldridge and Shelley F. J. Wickham, 238:8:1–8:22. Leibniz International
Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum
für Informatik, 2022. https://doi.org/10.4230/LIPIcs.DNA.28.8.'
ieee: 'A. Padalkin, C. Scheideler, and D. Warner, “The Structural Power of Reconfigurable
Circuits in the Amoebot Model,” in 28th International Conference on DNA Computing
and Molecular Programming (DNA 28), 2022, vol. 238, p. 8:1–8:22, doi: 10.4230/LIPIcs.DNA.28.8.'
mla: Padalkin, Andreas, et al. “The Structural Power of Reconfigurable Circuits
in the Amoebot Model.” 28th International Conference on DNA Computing and Molecular
Programming (DNA 28), edited by Thomas E. Ouldridge and Shelley F. J. Wickham,
vol. 238, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, p. 8:1–8:22,
doi:10.4230/LIPIcs.DNA.28.8.
short: 'A. Padalkin, C. Scheideler, D. Warner, in: T.E. Ouldridge, S.F.J. Wickham
(Eds.), 28th International Conference on DNA Computing and Molecular Programming
(DNA 28), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany,
2022, p. 8:1–8:22.'
date_created: 2022-08-08T17:32:19Z
date_updated: 2022-11-17T14:18:24Z
department:
- _id: '79'
doi: 10.4230/LIPIcs.DNA.28.8
editor:
- first_name: Thomas E.
full_name: Ouldridge, Thomas E.
last_name: Ouldridge
- first_name: Shelley F. J.
full_name: Wickham, Shelley F. J.
last_name: Wickham
intvolume: ' 238'
language:
- iso: eng
page: 8:1–8:22
place: Dagstuhl, Germany
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '2'
name: 'SFB 901 - A: SFB 901 - Project Area A'
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
- _id: '5'
name: 'SFB 901 - A1: SFB 901 - Subproject A1'
- _id: '13'
name: 'SFB 901 - C1: SFB 901 - Subproject C1'
publication: 28th International Conference on DNA Computing and Molecular Programming
(DNA 28)
publication_identifier:
isbn:
- 978-3-95977-253-2
issn:
- 1868-8969
publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: The Structural Power of Reconfigurable Circuits in the Amoebot Model
type: conference
user_id: '477'
volume: 238
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: '33230'
author:
- first_name: Joshua J.
full_name: Daymude, Joshua J.
last_name: Daymude
- first_name: Andréa W.
full_name: Richa, Andréa W.
last_name: Richa
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Daymude JJ, Richa AW, Scheideler C. Local Mutual Exclusion for Dynamic, Anonymous,
Bounded Memory Message Passing Systems. In: Aspnes J, Michail O, eds. 1st Symposium
on Algorithmic Foundations of Dynamic Networks, SAND 2022, March 28-30, 2022,
Virtual Conference. Vol 221. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2022:12:1–12:19. doi:10.4230/LIPIcs.SAND.2022.12'
apa: Daymude, J. J., Richa, A. W., & Scheideler, C. (2022). Local Mutual Exclusion
for Dynamic, Anonymous, Bounded Memory Message Passing Systems. In J. Aspnes &
O. Michail (Eds.), 1st Symposium on Algorithmic Foundations of Dynamic Networks,
SAND 2022, March 28-30, 2022, Virtual Conference (Vol. 221, p. 12:1–12:19).
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2022.12
bibtex: '@inproceedings{Daymude_Richa_Scheideler_2022, series={LIPIcs}, title={Local
Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems},
volume={221}, DOI={10.4230/LIPIcs.SAND.2022.12},
booktitle={1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND
2022, March 28-30, 2022, Virtual Conference}, publisher={Schloss Dagstuhl - Leibniz-Zentrum
für Informatik}, author={Daymude, Joshua J. and Richa, Andréa W. and Scheideler,
Christian}, editor={Aspnes, James and Michail, Othon}, year={2022}, pages={12:1–12:19},
collection={LIPIcs} }'
chicago: Daymude, Joshua J., Andréa W. Richa, and Christian Scheideler. “Local Mutual
Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems.” In
1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022, March
28-30, 2022, Virtual Conference, edited by James Aspnes and Othon Michail,
221:12:1–12:19. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
https://doi.org/10.4230/LIPIcs.SAND.2022.12.
ieee: 'J. J. Daymude, A. W. Richa, and C. Scheideler, “Local Mutual Exclusion for
Dynamic, Anonymous, Bounded Memory Message Passing Systems,” in 1st Symposium
on Algorithmic Foundations of Dynamic Networks, SAND 2022, March 28-30, 2022,
Virtual Conference, 2022, vol. 221, p. 12:1–12:19, doi: 10.4230/LIPIcs.SAND.2022.12.'
mla: Daymude, Joshua J., et al. “Local Mutual Exclusion for Dynamic, Anonymous,
Bounded Memory Message Passing Systems.” 1st Symposium on Algorithmic Foundations
of Dynamic Networks, SAND 2022, March 28-30, 2022, Virtual Conference, edited
by James Aspnes and Othon Michail, vol. 221, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022, p. 12:1–12:19, doi:10.4230/LIPIcs.SAND.2022.12.
short: 'J.J. Daymude, A.W. Richa, C. Scheideler, in: J. Aspnes, O. Michail (Eds.),
1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022, March
28-30, 2022, Virtual Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, p. 12:1–12:19.'
date_created: 2022-08-30T06:31:21Z
date_updated: 2022-08-30T06:33:44Z
department:
- _id: '79'
doi: 10.4230/LIPIcs.SAND.2022.12
editor:
- first_name: James
full_name: Aspnes, James
last_name: Aspnes
- first_name: Othon
full_name: Michail, Othon
last_name: Michail
intvolume: ' 221'
language:
- iso: eng
page: 12:1–12:19
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: 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022,
March 28-30, 2022, Virtual Conference
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
series_title: LIPIcs
status: public
title: Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing
Systems
type: conference
user_id: '15504'
volume: 221
year: '2022'
...