@misc{5404, author = {{Kolpaczki, Patrick Irenäus}}, publisher = {{Universität Paderborn}}, title = {{{Online Algorithmen für das k-Page Migration Problem}}}, year = {{2018}}, } @phdthesis{1209, abstract = {{My dissertation deals with the Gathering problem for swarms of n point-shaped robots on a grid, in which all robots of the swarm are supposed to gather at a previously undefined point. Special attention is paid to the strong limitation of robot capabilities. These include in particular the lack of global control, a global compass, global visibility and (global) communication skills. Furthermore, all robots are identical. The robots are given only local abilities. This includes a constant range of vision. The robots all work completely synchronously. In this work we present and analyze three different Gathering strategies in different robot models. We formally prove correctness and total running time: Chapter 4 focuses on minimizing the available robot capabilities. The underlying strategy completes the gathering in O(n^2) time. For the following Chapters 5 and 6, the aim is to optimize the total running time under using only local robot capabilities: We additionally allow a constant-sized memory and a constant number of locally visible statuses (lights, flags). For the strategies of both chapters we show an asymptotically optimal running time of O(n). Unlike in Chapters 4 and 5, we additionally restrict connectivity and vision to an initially given chain connectivity in Chapter 6, where two chain neighbors must have a distance of 1 from each other. A robot can only see and interact with a constant number of its direct chain neighbors.}}, author = {{Jung, Daniel}}, isbn = {{978-3-942647-99-1}}, publisher = {{Universität Paderborn}}, title = {{{Local Strategies for Swarm Formations on a Grid}}}, doi = {{10.17619/UNIPB/1-271}}, year = {{2018}}, } @inproceedings{2851, author = {{Markarian, Christine}}, booktitle = {{International Conference on Operations Research (OR)}}, location = {{Berlin}}, title = {{{Leasing with Uncertainty}}}, doi = {{10.1007/978-3-319-89920-6_57}}, year = {{2017}}, } @misc{18026, author = {{Burkhardt, Michél }}, publisher = {{Universität Paderborn}}, title = {{{Untersuchungen zum Cone-Hashing}}}, year = {{2017}}, } @misc{18028, author = {{Schenk, Andreas}}, publisher = {{Universität Paderborn}}, title = {{{Monotone Suchbarkeit in mehrdimensionalen verteilten Datenstrukturen}}}, year = {{2017}}, } @misc{18029, author = {{Beckendorf, Björn}}, publisher = {{Universität Paderborn}}, title = {{{Visualisierung zu Algorithmen verteilter Netzwerksysteme}}}, year = {{2017}}, } @misc{81, author = {{Luo, Linghui}}, publisher = {{Universität Paderborn}}, title = {{{MultiSkipList: A Self-stabilizing Overlay Network with Monotonic Searchability maintained}}}, year = {{2017}}, } @inproceedings{82, abstract = {{Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter.}}, author = {{Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}}, booktitle = {{Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)}}, pages = {{139--150}}, title = {{{Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity}}}, doi = {{10.1007/978-3-319-59605-1_13}}, year = {{2017}}, } @proceedings{5980, editor = {{Scheideler, Christian and Taghi Hajiaghayi, Mohammad}}, isbn = {{978-1-4503-4593-4}}, publisher = {{ACM}}, title = {{{Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017, Washington DC, USA, July 24-26, 2017}}}, doi = {{10.1145/3087556}}, year = {{2017}}, } @phdthesis{61, author = {{Strothmann, Thim Frederik}}, publisher = {{Universität Paderborn}}, title = {{{Self-* Algorithms for Distributed Systems}}}, doi = {{10.17619/UNIPB/1-150}}, year = {{2017}}, } @misc{699, author = {{Sundermeier, Jannik}}, publisher = {{Universität Paderborn}}, title = {{{Routing in Hybrid Communication Networks with Holes - Considering Bounding Boxes as Hole Abstractions}}}, year = {{2017}}, } @inproceedings{70, author = {{Feldkord, Björn and Markarian, Christine and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}}, pages = {{17 -- 31}}, title = {{{Price Fluctuations in Online Leasing}}}, doi = {{10.1007/978-3-319-71147-8_2}}, year = {{2017}}, } @misc{700, author = {{Knollmann, Till}}, publisher = {{Universität Paderborn}}, title = {{{A Self-Stabilizing Protocol for Graphs of Diameter Two}}}, year = {{2017}}, } @misc{701, author = {{Götte, Thorsten}}, publisher = {{Universität Paderborn}}, title = {{{Self-Stabilizing Spanners for Tree Metrics}}}, year = {{2017}}, } @inproceedings{55, abstract = {{We introduce the mobile server problem, inspired by current trends to move computational tasks from cloud structures to multiple devices close to the end user. An example for this are embedded systems in autonomous cars that communicate in order to coordinate their actions. Our model is a variant of the classical Page Migration Problem. Moreformally, we consider a mobile server holding a data page.The server can move in the Euclidean space (of arbitrary dimension). In every round, requests for data items from the page pop up at arbitrary points in the space. The requests are served, each at a cost of the distance from the requesting point and the server, and the mobile server may move, at a cost D times the distance traveled for some constant D . We assume a maximum distance m the server is allowed to move per round. We show that no online algorithm can achieve a competitive ratio independent of the length of the input sequence in this setting. Hence we augment the maximum movement distance of the online algorithms to ( 1 + δ) times the maximum distance of the offline solution. We provide a deterministic algorithm which is simple to describe and works for multiple variants of our problem. The algorithm achieves almost tight competitive ratios independent of the length of the input sequence.}}, author = {{Feldkord, Björn and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}}, pages = {{313--319}}, title = {{{The Mobile Server Problem}}}, doi = {{10.1145/3087556.3087575}}, year = {{2017}}, } @misc{696, author = {{Wachowiak, Lennart}}, publisher = {{Universität Paderborn}}, title = {{{Das Mobile Server Problem in Netzwerken}}}, year = {{2017}}, } @misc{697, author = {{Burkhardt, Michel}}, publisher = {{Universität Paderborn}}, title = {{{Untersuchungen zum Cone-Hashing}}}, year = {{2017}}, } @misc{1048, author = {{Schenk, Andreas}}, publisher = {{Universität Paderborn}}, title = {{{Monotone Suchbarkeit in mehrdimensionalen verteilten Datenstrukturen}}}, year = {{2017}}, } @misc{1049, author = {{Beckendorfer, Björn}}, publisher = {{Universität Paderborn}}, title = {{{Visualisierung zu Algorithmen verteilter Netzwerksysteme}}}, year = {{2017}}, } @inproceedings{105, abstract = {{We initiate the study of network monitoring algorithms in a class of hybrid networks in which the nodes are connected by an external network and an internal network (as a short form for externally and internally controlled network). While the external network lies outside of the control of the nodes (or in our case, the monitoring protocol running in them) and might be exposed to continuous changes, the internal network is fully under the control of the nodes. As an example, consider a group of users with mobile devices having access to the cell phone infrastructure. While the network formed by the WiFi connections of the devices is an external network (as its structure is not necessarily under the control of the monitoring protocol), the connections between the devices via the cell phone infrastructure represent an internal network (as it can be controlled by the monitoring protocol). Our goal is to continuously monitor properties of the external network with the help of the internal network. We present scalable distributed algorithms that efficiently monitor the number of edges, the average node degree, the clustering coefficient, the bipartiteness, and the weight of a minimum spanning tree. Their performance bounds demonstrate that monitoring the external network state with the help of an internal network can be done much more efficiently than just using the external network, as is usually done in the literature.}}, author = {{Gmyr, Robert and Hinnenthal, Kristian and Scheideler, Christian and Sohler, Christian}}, booktitle = {{Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)}}, pages = {{137:1----137:15}}, title = {{{Distributed Monitoring of Network Properties: The Power of Hybrid Networks}}}, doi = {{10.4230/LIPIcs.ICALP.2017.137}}, year = {{2017}}, }