@article{1369,
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},
issn = {1382-6905},
journal = {Journal of Combinatorial Optimization},
publisher = {Springer Nature},
title = {{Pure Nash equilibria in restricted budget games}},
doi = {10.1007/s10878-018-0269-7},
year = {2018},
}
@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},
}
@article{2848,
author = {Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm},
journal = {Algorithmica},
number = {5},
pages = {1556–1574},
publisher = {Springer},
title = {{Towards Flexible Demands in Online Leasing Problems. }},
doi = {10.1007/s00453-018-0420-y},
volume = {80},
year = {2018},
}
@inproceedings{4375,
abstract = {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.\\
The network is the same for each dimension, namely a distance halving network like the one introduced by Naor and Wieder (ACM TALG'07).
We 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.
Furthermore, 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.
Our algorithms are based on a mapping of the Hilbert Curve through $[m]^d$ to the peers.},
author = {Benter, Markus and Knollmann, Till and Meyer auf der Heide, Friedhelm and Setzer, Alexander and Sundermeier, Jannik},
booktitle = {Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)},
keyword = {Distributed Storage, Multi-Dimensional Range Queries, Peer-to-Peer, Hilbert Curve},
location = {Helsinki},
title = {{A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension}},
doi = {10.1007/978-3-030-19759-9_4},
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{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{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{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},
}
@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},
}
@misc{1188,
author = {Kempf, Jérôme},
publisher = {Universität Paderborn},
title = {{Learning deterministic bandit behaviour form compositions}},
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},
}
@phdthesis{1209,
author = {Jung, Daniel},
publisher = {Universität Paderborn},
title = {{Local Strategies for Swarm Formations on a Grid}},
doi = {10.17619/UNIPB/1-271},
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},
}
@misc{5403,
author = {Geromel, Marcel},
title = {{Mobile Facility Leasing}},
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},
}
@article{706,
author = {Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören},
journal = {Journal of Combinatorial Optimization},
number = {4},
pages = {1168--1194},
publisher = {Springer},
title = {{Cost-efficient Scheduling on Machines from the Cloud}},
doi = {10.1007/s10878-017-0198-x},
volume = {36},
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},
}
@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},
}