@inproceedings{4565,
author = {Jung, Daniel and Kolb, Christina and Scheideler, Christian and Sundermeier, Jannik},
booktitle = {Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA)},
isbn = {9781450357999},
location = {Wien},
publisher = {ACM Press},
title = {{Brief Announcement: Competitive Routing in Hybrid Communication Networks}},
doi = {10.1145/3210377.3210663},
year = {2018},
}
@misc{1187,
author = {Nachtigall, Marcel},
publisher = {Universität Paderborn},
title = {{Scenario-driven Strategy Analysis in a n-player Composition Game Model}},
year = {2018},
}
@article{2849,
author = {Abu-Khzam, Faisal N. and Markarian, Christine and Meyer auf der Heide, Friedhelm and Schubert, Michael},
journal = {Theory of Computing Systems},
publisher = {Springer},
title = {{Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks}},
doi = {10.1007/s00224-017-9836-z},
year = {2018},
}
@article{3551,
author = {König, Jürgen and Mäcker, Alexander and Meyer auf der Heide, Friedhelm and Riechers, Sören},
journal = {Journal of Combinatorial Optimization},
number = {4},
pages = {1356--1379},
title = {{Scheduling with interjob communication on parallel processors}},
doi = {10.1007/s10878-018-0325-3},
volume = {36},
year = {2018},
}
@article{669,
abstract = {We study a new class of games which generalizes congestion games andits bottleneck variant. We introduce congestion games with mixed objectives to modelnetwork scenarios in which players seek to optimize for latency and bandwidths alike.We characterize the (non-)existence of pure Nash equilibria (PNE), the convergenceof improvement dynamics, the quality of equilibria and show the complexity of thedecision problem. For games that do not possess PNE we give bounds on the approx-imation ratio of approximate pure Nash equilibria.},
author = {Feldotto, Matthias and Leder, Lennart and Skopalik, Alexander},
issn = {1382-6905},
journal = {Journal of Combinatorial Optimization},
number = {4},
pages = {1145--1167},
publisher = {Springer Nature},
title = {{Congestion games with mixed objectives}},
doi = {10.1007/s10878-017-0189-y},
volume = {36},
year = {2018},
}
@article{63,
author = {Althaus, Ernst and Brinkmann, Andre and Kling, Peter and Meyer auf der Heide, Friedhelm and Nagel, Lars and Riechers, Sören and Sgall, Jiri and Süß, Tim},
journal = {Journal of Scheduling},
number = {1},
pages = {77--92},
publisher = {Springer},
title = {{Scheduling Shared Continuous Resources on Many-Cores}},
doi = {10.1007/s10951-017-0518-0},
volume = {21},
year = {2018},
}
@inproceedings{17651,
abstract = {Consider mitigating the effects of denial of service or of malicious traffic in networks by deleting edges. Edge deletion reduces the DoS or the number of the malicious flows, but it also inadvertently removes some of the desired flows. To model this important problem, we formulate two problems: (1) remove all the undesirable flows while minimizing the damage to the desirable ones and (2) balance removing the undesirable flows and not removing too many of the desirable flows. We prove these problems are equivalent to important theoretical problems, thereby being important not only practically but also theoretically, and very hard to approximate in a general network. We employ reductions to nonetheless approximate the problem and also provide a greedy approximation. When the network is a tree, the problems are still MAX SNP-hard, but we provide a greedy-based 2l-approximation algorithm, where l is the longest desirable flow. We also provide an algorithm, approximating the first and the second problem within {\$}{\$}2 {\backslash}sqrt{\{} 2{\backslash}left| E {\backslash}right| {\}}{\$}{\$}and {\$}{\$}2 {\backslash}sqrt{\{}2 ({\backslash}left| E {\backslash}right| + {\backslash}left| {\backslash}text {\{}undesirable flows{\}} {\backslash}right| ){\}}{\$}{\$}, respectively, where E is the set of the edges of the network. We also provide a fixed-parameter tractable (FPT) algorithm. Finally, if the tree has a root such that every flow in the tree flows on the path from the root to a leaf, we solve the problem exactly using dynamic programming.},
author = {Polevoy, Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees},
booktitle = {Combinatorial Optimization and Applications},
editor = {Kim, Donghyun and Uma, R. N. and Zelikovsky, Alexander},
isbn = {978-3-030-04651-4},
keyword = {flow, Red-Blue Set Cover, Positive-Negative Partial Set Cover, approximation, tree, MAX SNP-hard, root, leaf, dynamic programming, FPT},
pages = {217--232},
publisher = {Springer International Publishing},
title = {{Removing Undesirable Flows by Edge Deletion}},
year = {2018},
}
@misc{1188,
author = {Kempf, Jérôme},
publisher = {Universität Paderborn},
title = {{Learning deterministic bandit behaviour form compositions}},
year = {2018},
}
@inproceedings{2484,
abstract = {We study the classic bin packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio while repacking items sparingly between updates. Formally, each item i has a movement cost c_i >= 0, and we want to use alpha * OPT bins and incur a movement cost gamma * c_i, either in the worst case, or in an amortized sense, for alpha, gamma as small as possible. We call gamma the recourse of the algorithm. This is motivated by cloud storage applications, where fully-dynamic bin packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure.},
author = {Feldkord, Björn and Feldotto, Matthias and Gupta, Anupam and Guruganesh, Guru and Kumar, Amit and Riechers, Sören and Wajc, David},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, Dániel and Sannella, Donald},
isbn = {978-3-95977-076-7},
issn = {1868-8969},
location = {Prag},
pages = {51:1--51:24},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
title = {{Fully-Dynamic Bin Packing with Little Repacking}},
doi = {10.4230/LIPIcs.ICALP.2018.51},
volume = {107},
year = {2018},
}
@inproceedings{4411,
abstract = {While a lot of research in distributed computing has covered solutions for self-stabilizing computing and topologies, there is far less work on self-stabilization for distributed data structures.
Considering crashing peers in peer-to-peer networks, it should not be taken for granted that a distributed data structure remains intact.
In this work, we present a self-stabilizing protocol for a distributed data structure called the hashed Patricia Trie (Kniesburges and Scheideler WALCOM'11) that enables efficient prefix search on a set of keys.
The data structure has a wide area of applications including string matching problems while offering low overhead and efficient operations when embedded on top of a distributed hash table.
Especially, longest prefix matching for $x$ can be done in $\mathcal{O}(\log |x|)$ hash table read accesses.
We show how to maintain the structure in a self-stabilizing way.
Our protocol assures low overhead in a legal state and a total (asymptotically optimal) memory demand of $\Theta(d)$ bits, where $d$ is the number of bits needed for storing all keys.},
author = {Knollmann, Till and Scheideler, Christian},
booktitle = {Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)},
editor = {Izumi, Taisuke and Kuznetsov, Petr},
keyword = {Self-Stabilizing, Prefix Search, Distributed Data Structure},
location = {Tokyo},
publisher = {Springer, Cham},
title = {{A Self-Stabilizing Hashed Patricia Trie}},
doi = {10.1007/978-3-030-03232-6_1},
volume = {11201},
year = {2018},
}
@inproceedings{2485,
author = {Feldkord, Björn and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
location = {Wien},
pages = {373 -- 381 },
publisher = {ACM},
title = {{Online Facility Location with Mobile Facilities}},
doi = {10.1145/3210377.3210389},
year = {2018},
}
@misc{3851,
author = {Koop, Samuel},
publisher = {Universität Paderborn},
title = {{Congestion Games mit gewichteten Strategien}},
year = {2018},
}
@misc{5403,
author = {Geromel, Marcel},
publisher = {Universität Paderborn},
title = {{Mobile Facility Leasing}},
year = {2018},
}
@inproceedings{4563,
abstract = {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.
In 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.
},
author = {Jung, Daniel and Kolb, Christina and Scheideler, Christian and Sundermeier, Jannik},
booktitle = {Proceedings of the 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) },
keyword = {greedy routing, ad hoc networks, convex hulls, c-competitiveness},
location = {Helsinki},
publisher = {Springer},
title = {{Competitive Routing in Hybrid Communication Networks}},
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{112,
abstract = {We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study $L_p$ norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.},
author = {Feldotto, Matthias and Leder, Lennart and Skopalik, Alexander},
booktitle = {Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC)},
pages = {222----233},
title = {{Congestion Games with Complementarities}},
doi = {10.1007/978-3-319-57586-5_19},
year = {2017},
}
@inproceedings{16339,
abstract = {In der CAD-unterstützten Entwicklung von technischen Systemen (Maschinen, Anlagen etc.) werden virtuelle Prototypen im Rahmen eines virtuellen Design-Reviews mit Hilfe eines VR-Systems gesamtheitlich betrachtet, um frühzeitig Fehler und Verbesserungsbedarf zu erkennen. Ein wichtiger Untersuchungsgegenstand ist dabei die Analyse von Transportwegen für den Materialtransport mittels Fließbändern, Förderketten oder schienenbasierten Transportsystemen. Diese Transportwege werden im VR-System animiert. Problematisch dabei ist, dass derartige Transportsysteme im zugrundeliegenden CAD-Modell in der Praxis oft nicht modelliert und nur exemplarisch angedeutet werden, da diese für die Konstruktion nicht relevant sind (z.B. der Fördergurt eines Förderbandes, oder die Kette einer Förderkette), oder die Informationen über den Verlauf bei der Konvertierung der Daten in das VR-System verloren gehen. Bei der Animation dieser Transportsysteme in einem VR-System muss der Transportweg also aufwändig, manuell nachgearbeitet werden. Das Ziel dieser Arbeit ist die Reduzierung des notwendigen manuellen Nachbearbeitungsaufwandes für das Design-Review durch eine automatische Berechnung der Animationspfade entlang eines Transportsystems. Es wird ein Algorithmus vorgestellt, der es ermöglicht mit nur geringem zeitlichem Benutzeraufwand den Animationspfad aus den reinen polygonalen dreidimensionalen Daten eines Transportsystems automatisch zu rekonstruieren.},
author = {Brandt, Sascha and Fischer, Matthias},
booktitle = {Wissenschaftsforum Intelligente Technische Systeme (WInTeSys) 2017},
location = {Paderborn},
pages = {415--427},
publisher = {Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn},
title = {{Automatische Ableitung der Transportwege von Transportsystemen aus dem 3D-Polygonmodell}},
volume = {369},
year = {2017},
}
@inproceedings{59,
abstract = {We consider a scheduling problem on $m$ identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each job $j$ comes with a size $p_j \in \mathbb{R}$ and a resource requirement $r_j > 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan.Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed).},
author = {Kling, Peter and Mäcker, Alexander and Riechers, Sören and Skopalik, Alexander},
booktitle = {Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
pages = {123----132},
title = {{Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource}},
doi = {10.1145/3087556.3087578},
year = {2017},
}
@inproceedings{66,
abstract = {In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of each player who chose that resource equals his demand. Otherwise, the budget is shared proportionally. In the general case, pure Nash equilibria (NE) do not exist for such games. In this paper, we consider the natural classes of singleton and matroid budget games with additional constraints and show that for each, pure NE can be guaranteed. In addition, we introduce a lexicographical potential function to prove that every matroid budget game has an approximate pure NE which depends on the largest ratio between the different demands of each individual player.},
author = {Drees, Maximilian and Feldotto, Matthias and Riechers, Sören and Skopalik, Alexander},
booktitle = {Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON)},
pages = {175----187},
title = {{Pure Nash Equilibria in Restricted Budget Games}},
doi = {10.1007/978-3-319-62389-4_15},
year = {2017},
}
@inbook{16461,
author = {Bemmann, Pascal and Biermeier, Felix and Bürmann, Jan and Kemper, Arne and Knollmann, Till and Knorr, Steffen and Kothe, Nils and Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören and Schaefer, Johannes and Sundermeier, Jannik},
booktitle = {Structural Information and Communication Complexity},
isbn = {9783319720494},
issn = {0302-9743},
title = {{Monitoring of Domain-Related Problems in Distributed Data Streams}},
doi = {10.1007/978-3-319-72050-0_13},
year = {2017},
}