@article{61172,
  author       = {{Coy, Sam and Czumaj, Artur and Scheideler, Christian and Schneider, Philipp and Werthmann, Julian}},
  issn         = {{0304-3975}},
  journal      = {{Theoretical Computer Science}},
  publisher    = {{Elsevier BV}},
  title        = {{{Routing Schemes for Hybrid Communication Networks}}},
  doi          = {{10.1016/j.tcs.2023.114352}},
  volume       = {{985}},
  year         = {{2024}},
}

@book{45863,
  abstract     = {{In the proposal for our CRC in 2011, we formulated a vision of markets for
IT services that describes an approach to the provision of such services
that was novel at that time and, to a large extent, remains so today:
„Our vision of on-the-fly computing is that of IT services individually and
automatically configured and brought to execution from flexibly combinable
services traded on markets. At the same time, we aim at organizing
markets whose participants maintain a lively market of services through
appropriate entrepreneurial actions.“
Over the last 12 years, we have developed methods and techniques to
address problems critical to the convenient, efficient, and secure use of
on-the-fly computing. Among other things, we have made the description
of services more convenient by allowing natural language input,
increased the quality of configured services through (natural language)
interaction and more efficient configuration processes and analysis
procedures, made the quality of (the products of) providers in the
marketplace transparent through reputation systems, and increased the
resource efficiency of execution through reconfigurable heterogeneous
computing nodes and an integrated treatment of service description and
configuration. We have also developed network infrastructures that have
a high degree of adaptivity, scalability, efficiency, and reliability, and
provide cryptographic guarantees of anonymity and security for market
participants and their products and services.
To demonstrate the pervasiveness of the OTF computing approach, we
have implemented a proof-of-concept for OTF computing that can run
typical scenarios of an OTF market. We illustrated the approach using
a cutting-edge application scenario – automated machine learning (AutoML).
Finally, we have been pushing our work for the perpetuation of
On-The-Fly Computing beyond the SFB and sharing the expertise gained
in the SFB in events with industry partners as well as transfer projects.
This work required a broad spectrum of expertise. Computer scientists
and economists with research interests such as computer networks and
distributed algorithms, security and cryptography, software engineering
and verification, configuration and machine learning, computer engineering
and HPC, microeconomics and game theory, business informatics
and management have successfully collaborated here.}},
  author       = {{Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm and Platzner, Marco and Wachsmuth, Henning and Wehrheim, Heike}},
  pages        = {{247}},
  publisher    = {{Heinz Nixdorf Institut, Universität Paderborn}},
  title        = {{{On-The-Fly Computing -- Individualized IT-services in dynamic markets}}},
  doi          = {{10.17619/UNIPB/1-1797}},
  volume       = {{412}},
  year         = {{2023}},
}

@article{43109,
  author       = {{Götte, Thorsten and Kolb, Christina and Scheideler, Christian and Werthmann, Julian}},
  journal      = {{Theor. Comput. Sci.}},
  pages        = {{113756}},
  title        = {{{Beep-and-Sleep: Message and Energy Efficient Set Cover}}},
  doi          = {{10.1016/j.tcs.2023.113756}},
  volume       = {{950}},
  year         = {{2023}},
}

@misc{44735,
  author       = {{Schweichhart, Jonas}},
  title        = {{{Minimum Edge Cuts in Overlay Networks}}},
  year         = {{2023}},
}

@inproceedings{45188,
  author       = {{Werthmann, Julian and Scheideler, Christian and Coy, Sam and Czumaj, Artur and Schneider, Philipp}},
  title        = {{{Routing Schemes for Hybrid Communication Networks}}},
  doi          = {{10.48550/ARXIV.2210.05333}},
  year         = {{2023}},
}

@article{45192,
  author       = {{Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian and Werthmann, Julian}},
  journal      = {{Distributed Computing}},
  title        = {{{Time-Optimal Construction of Overlays}}},
  doi          = {{https://doi.org/10.1007/s00446-023-00442-4}},
  year         = {{2023}},
}

@phdthesis{45580,
  author       = {{Castenow, Jannik}},
  title        = {{{Local Protocols for Contracting and Expanding Robot Formation Problems}}},
  doi          = {{10.17619/UNIPB/1-1750}},
  year         = {{2023}},
}

@phdthesis{45579,
  author       = {{Knollmann, Till}},
  title        = {{{Online Algorithms for Allocating Heterogeneous Resources}}},
  doi          = {{10.17619/UNIPB/1-1751}},
  year         = {{2023}},
}

@inbook{45875,
  author       = {{Götte, Thorsten and Knollmann, Till and Meyer auf der Heide, Friedhelm and Scheideler, Christian and Werthmann, Julian}},
  booktitle    = {{On-The-Fly Computing -- Individualized IT-services in dynamic markets}},
  editor       = {{Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm and Platzner, Marco and Wachsmuth, Henning and Wehrheim, Heike}},
  pages        = {{1----20}},
  publisher    = {{Heinz Nixdorf Institut, Universität Paderborn}},
  title        = {{{Capabilities and Limitations of Local Strategies in Dynamic Networks}}},
  doi          = {{10.5281/zenodo.8060372}},
  volume       = {{412}},
  year         = {{2023}},
}

@misc{46110,
  author       = {{Ashri, Nivedita}},
  title        = {{{Virtual On-Demand Volunteer System Based on Delaunay Triangulation}}},
  year         = {{2023}},
}

@misc{47134,
  author       = {{Deppe, Volker}},
  title        = {{{Routing in Hypergraphs}}},
  year         = {{2023}},
}

@inproceedings{45193,
  author       = {{Dou, Jinfeng and Götte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian}},
  booktitle    = {{Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC '23)}},
  location     = {{Orlando, USA}},
  title        = {{{Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs}}},
  year         = {{2023}},
}

@misc{30152,
  author       = {{Roopa, Rajanna}},
  title        = {{{Evaluation of Algorithms for the Node Capacitated Clique}}},
  year         = {{2022}},
}

@misc{30199,
  author       = {{Nachtigall, Marcel}},
  title        = {{{Hybrid Routing in Three Dimensions}}},
  year         = {{2022}},
}

@misc{31947,
  author       = {{Hillebrandt, Henning}},
  title        = {{{Verteiltes Berechnen kompakter Routingtabellen in Unit Disk Graphen}}},
  year         = {{2022}},
}

@inproceedings{31847,
  abstract     = {{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).

In 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$.

We 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.
    
The 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       = {{Castenow, Jannik and Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}},
  booktitle    = {{Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures}},
  isbn         = {{9781450391467}},
  keywords     = {{K-Server Problem, Heterogeneity, Online Caching}},
  pages        = {{345--356}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{The k-Server with Preferences Problem}}},
  doi          = {{10.1145/3490148.3538595}},
  year         = {{2022}},
}

@inproceedings{32602,
  author       = {{Padalkin, Andreas and Scheideler, Christian and Warner, Daniel}},
  booktitle    = {{28th International Conference on DNA Computing and Molecular Programming (DNA 28)}},
  editor       = {{Ouldridge, Thomas E. and Wickham, Shelley F. J.}},
  isbn         = {{978-3-95977-253-2}},
  issn         = {{1868-8969}},
  pages        = {{8:1–8:22}},
  publisher    = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}},
  title        = {{{The Structural Power of Reconfigurable Circuits in the Amoebot Model}}},
  doi          = {{10.4230/LIPIcs.DNA.28.8}},
  volume       = {{238}},
  year         = {{2022}},
}

@article{31479,
  author       = {{Baswana, Surender and Gupta, Shiv and Knollmann, Till}},
  issn         = {{0178-4617}},
  journal      = {{Algorithmica}},
  keywords     = {{Applied Mathematics, Computer Science Applications, General Computer Science}},
  publisher    = {{Springer Science and Business Media LLC}},
  title        = {{{Mincut Sensitivity Data Structures for the Insertion of an Edge}}},
  doi          = {{10.1007/s00453-022-00978-0}},
  year         = {{2022}},
}

@inproceedings{33230,
  author       = {{Daymude, Joshua J. and Richa, Andréa W. and Scheideler, Christian}},
  booktitle    = {{1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022, March 28-30, 2022, Virtual Conference}},
  editor       = {{Aspnes, James and Michail, Othon}},
  pages        = {{12:1–12:19}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  title        = {{{Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems}}},
  doi          = {{10.4230/LIPIcs.SAND.2022.12}},
  volume       = {{221}},
  year         = {{2022}},
}

@inproceedings{33967,
  author       = {{Aguiliera, Marcos and Richa, Andréa W. and Schwarzmann, Alexander A. and Panconesi, Alessandro and Scheideler, Christian and Woelfel, Philipp}},
  booktitle    = {{PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022}},
  editor       = {{Milani, Alessia and Woelfel, Philipp}},
  pages        = {{1}},
  publisher    = {{ACM}},
  title        = {{{2022 Edsger W. Dijkstra Prize in Distributed Computing}}},
  doi          = {{10.1145/3519270.3538411}},
  year         = {{2022}},
}