@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)}},
keywords = {{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{5403,
author = {{Geromel, Marcel}},
publisher = {{Universität Paderborn}},
title = {{{Mobile Facility Leasing}}},
year = {{2018}},
}
@misc{5404,
author = {{Kolpaczki, Patrick Irenäus}},
publisher = {{Universität Paderborn}},
title = {{{Online Algorithmen für das k-Page Migration Problem}}},
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}},
}
@misc{1186,
author = {{Kemper, Arne}},
publisher = {{Universität Paderborn}},
title = {{{Pure Nash Equilibria in Robust Congestion Games via Potential Functions}}},
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}},
}
@misc{1188,
author = {{Kempf, Jérôme}},
publisher = {{Universität Paderborn}},
title = {{{Learning deterministic bandit behaviour form compositions}}},
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}},
}
@inbook{16392,
author = {{Feldkord, Björn and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}},
booktitle = {{Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications}},
isbn = {{9783319125671}},
issn = {{0302-9743}},
title = {{{A Dynamic Distributed Data Structure for Top-k and k-Select Queries}}},
doi = {{10.1007/978-3-319-98355-4_18}},
year = {{2018}},
}
@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}},
}
@phdthesis{19604,
author = {{Li, Shouwei}},
title = {{{Parallel fixed parameter tractable problems}}},
doi = {{10.17619/UNIPB/1-252}},
year = {{2017}},
}
@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}},
}
@inproceedings{24398,
abstract = {{Through this study, we introduce the idea of applying scheduling techniques to allocate spatial resources that are shared among multiple robots moving in a static environment and having temporal constraints on the arrival time to destinations. To illustrate this idea, we present an exemplified algorithm that plans and assigns a motion path to each robot. The considered problem is particularly challenging because: (i) the robots share the same environment and thus the planner must take into account overlapping paths which cannot happen at the same time; (ii) there are time deadlines thus the planner must deal with temporal constraints; (iii) new requests arrive without a priori knowledge thus the planner must be able to add new paths online and adjust old plans; (iv) the robot motion is subject to noise thus the planner must be reactive to adapt to online changes. We showcase the functioning of the proposed algorithm through a set of agent-based simulations.}},
author = {{Khaluf, Yara and Markarian, Christine and Simoens, Pieter and Reina, Andreagiovanni}},
booktitle = {{International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS 2017)}},
issn = {{0302-9743}},
title = {{{Scheduling Access to Shared Space in Multi-robot Systems}}},
doi = {{10.1007/978-3-319-59930-4_12}},
year = {{2017}},
}
@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{113,
abstract = {{We study the computation of approximate pure Nash equilibria in Shapley value (SV) weighted congestion games, introduced in [19]. This class of games considers weighted congestion games in which Shapley values are used as an alternative (to proportional shares) for distributing the total cost of each resource among its users. We focus on the interesting subclass of such games with polynomial resource cost functions and present an algorithm that computes approximate pure Nash equilibria with a polynomial number of strategy updates. Since computing a single strategy update is hard, we apply sampling techniques which allow us to achieve polynomial running time. The algorithm builds on the algorithmic ideas of [7], however, to the best of our knowledge, this is the first algorithmic result on computation of approximate equilibria using other than proportional shares as player costs in this setting. We present a novel relation that approximates the Shapley value of a player by her proportional share and vice versa. As side results, we upper bound the approximate price of anarchy of such games and significantly improve the best known factor for computing approximate pure Nash equilibria in weighted congestion games of [7].}},
author = {{Feldotto, Matthias and Gairing, Martin and Kotsialou, Grammateia and Skopalik, Alexander}},
booktitle = {{Proceedings of the 13th International Conference on Web and Internet Economics (WINE)}},
title = {{{Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games}}},
doi = {{10.1007/978-3-319-71924-5_14}},
year = {{2017}},
}
@inproceedings{17652,
author = {{Polevoy, Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}},
booktitle = {{Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I}},
isbn = {{978-3-319-71150-8}},
keywords = {{flow, filter, MMSA, set cover, approximation, local ratio algorithm}},
pages = {{3--17}},
publisher = {{Springer International Publishing}},
title = {{{Filtering Undesirable Flows in Networks}}},
doi = {{10.1007/978-3-319-71150-8_1}},
year = {{2017}},
}
@inproceedings{17653,
author = {{Polevoy, Gleb and de Weerdt, M.M.}},
booktitle = {{Proceedings of the 29th Benelux Conference on Artificial Intelligence}},
keywords = {{interaction, reciprocation, contribute, shared effort, curbing, convergence, threshold, Nash equilibrium, social welfare, efficiency, price of anarchy, price of stability}},
publisher = {{Springer}},
title = {{{Reciprocation Effort Games}}},
year = {{2017}},
}
@inproceedings{17654,
author = {{Polevoy, Gleb and de Weerdt, M.M.}},
booktitle = {{Proceedings of the 29th Benelux Conference on Artificial Intelligence}},
keywords = {{agents, projects, contribute, shared effort game, competition, quota, threshold, Nash equilibrium, social welfare, efficiency, price of anarchy, price of stability}},
publisher = {{Springer}},
title = {{{Competition between Cooperative Projects}}},
year = {{2017}},
}
@unpublished{17811,
abstract = {{We consider a swarm of $n$ autonomous mobile robots, distributed on a
2-dimensional grid. A basic task for such a swarm is the gathering process: All
robots have to gather at one (not predefined) place. A common local model for
extremely simple robots is the following: The robots do not have a common
compass, only have a constant viewing radius, are autonomous and
indistinguishable, can move at most a constant distance in each step, cannot
communicate, are oblivious and do not have flags or states. The only gathering
algorithm under this robot model, with known runtime bounds, needs
$\mathcal{O}(n^2)$ rounds and works in the Euclidean plane. The underlying time
model for the algorithm is the fully synchronous $\mathcal{FSYNC}$ model. On
the other side, in the case of the 2-dimensional grid, the only known gathering
algorithms for the same time and a similar local model additionally require a
constant memory, states and "flags" to communicate these states to neighbors in
viewing range. They gather in time $\mathcal{O}(n)$.
In this paper we contribute the (to the best of our knowledge) first
gathering algorithm on the grid that works under the same simple local model as
the above mentioned Euclidean plane strategy, i.e., without memory (oblivious),
"flags" and states. We prove its correctness and an $\mathcal{O}(n^2)$ time
bound in the fully synchronous $\mathcal{FSYNC}$ time model. This time bound
matches the time bound of the best known algorithm for the Euclidean plane
mentioned above. We say gathering is done if all robots are located within a
$2\times 2$ square, because in $\mathcal{FSYNC}$ such configurations cannot be
solved.}},
author = {{Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm}},
booktitle = {{arXiv:1702.03400}},
title = {{{Gathering Anonymous, Oblivious Robots on a Grid}}},
year = {{2017}},
}
@inproceedings{79,
abstract = {{Consider a problem in which $n$ jobs that are classified into $k$ types arrive over time at their release times and are to be scheduled on a single machine so as to minimize the maximum flow time.The machine requires a setup taking $s$ time units whenever it switches from processing jobs of one type to jobs of a different type.We consider the problem as an online problem where each job is only known to the scheduler as soon as it arrives and where the processing time of a job only becomes known upon its completion (non-clairvoyance).We are interested in the potential of simple ``greedy-like'' algorithms.We analyze a modification of the FIFO strategy and show its competitiveness to be $\Theta(\sqrt{n})$, which is optimal for the considered class of algorithms.For $k=2$ types it achieves a constant competitiveness.Our main insight is obtained by an analysis of the smoothed competitiveness.If processing times $p_j$ are independently perturbed to $\hat p_j = (1+X_j)p_j$, we obtain a competitiveness of $O(\sigma^{-2} \log^2 n)$ when $X_j$ is drawn from a uniform or a (truncated) normal distribution with standard deviation $\sigma$.The result proves that bad instances are fragile and ``practically'' one might expect a much better performance than given by the $\Omega(\sqrt{n})$-bound.}},
author = {{Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}},
booktitle = {{Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)}},
pages = {{207--222}},
publisher = {{Springer}},
title = {{{Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times}}},
doi = {{10.1007/978-3-319-89441-6}},
volume = {{10787}},
year = {{2017}},
}