TY - CHAP
AU - Bemmann, Pascal
AU - Biermeier, Felix
AU - Bürmann, Jan
AU - Kemper, Arne
AU - Knollmann, Till
AU - Knorr, Steffen
AU - Kothe, Nils
AU - Mäcker, Alexander
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
AU - Riechers, Sören
AU - Schaefer, Johannes
AU - Sundermeier, Jannik
ID - 16461
SN - 0302-9743
T2 - Structural Information and Communication Complexity
TI - Monitoring of Domain-Related Problems in Distributed Data Streams
ER -
TY - GEN
AU - Bürmann, Jan
ID - 1080
TI - Complexity of Signalling in Routing Games under Uncertainty
ER -
TY - GEN
AU - Nachtigall, Simon
ID - 1073
TI - Sortieren dynamischer Daten
ER -
TY - CONF
AB - 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].
AU - Feldotto, Matthias
AU - Gairing, Martin
AU - Kotsialou, Grammateia
AU - Skopalik, Alexander
ID - 113
T2 - Proceedings of the 13th International Conference on Web and Internet Economics (WINE)
TI - Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games
ER -
TY - CONF
AU - Fischer, Matthias
AU - Jung, Daniel
AU - Meyer auf der Heide, Friedhelm
ED - Fernández Anta, Antonio
ED - Jurdzinski, Tomasz
ED - Mosteiro, Miguel A.
ED - Zhang, Yanyong
ID - 16347
T2 - Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}
TI - Gathering Anonymous, Oblivious Robots on a Grid
VL - 10718
ER -
TY - CONF
AB - 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.
AU - Feldkord, Björn
AU - Meyer auf der Heide, Friedhelm
ID - 55
T2 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
TI - The Mobile Server Problem
ER -
TY - CONF
AB - 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.
AU - Mäcker, Alexander
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
AU - Riechers, Sören
ID - 79
T2 - Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)
TI - Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times
VL - 10787
ER -
TY - GEN
AU - Vijayalakshmi, Vipin Ravindran
ID - 1081
TI - Bounding the Inefficiency of Equilibria in Congestion Games under Taxation
ER -
TY - GEN
AU - Pukrop, Simon
ID - 1074
TI - Robuste Optimierung in Congestion Games
ER -
TY - CONF
AU - Biermeier, Felix
AU - Feldkord, Björn
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
ID - 16348
T2 - Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)
TI - A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries
ER -