TY - GEN AU - Kempf, Jérôme ID - 1188 TI - Learning deterministic bandit behaviour form compositions ER - TY - THES AB - 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. AU - Jung, Daniel ID - 1209 SN - 978-3-942647-99-1 TI - Local Strategies for Swarm Formations on a Grid ER - TY - CHAP AU - Feldkord, Björn AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm ID - 16392 SN - 0302-9743 T2 - Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications TI - A Dynamic Distributed Data Structure for Top-k and k-Select Queries ER - TY - JOUR AB - 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. AU - Drees, Maximilian AU - Feldotto, Matthias AU - Riechers, Sören AU - Skopalik, Alexander ID - 1369 JF - Journal of Combinatorial Optimization SN - 1382-6905 TI - Pure Nash equilibria in restricted budget games ER - TY - THES AU - Li, Shouwei ID - 19604 TI - Parallel fixed parameter tractable problems ER - TY - CONF AU - Markarian, Christine ID - 2851 T2 - International Conference on Operations Research (OR) TI - Leasing with Uncertainty ER - TY - CONF AB - 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. AU - Khaluf, Yara AU - Markarian, Christine AU - Simoens, Pieter AU - Reina, Andreagiovanni ID - 24398 SN - 0302-9743 T2 - International Conference on Practical Applications of Agents and Multi-Agent Systems (PAAMS 2017) TI - Scheduling Access to Shared Space in Multi-robot Systems ER - TY - CONF AB - 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. AU - Feldotto, Matthias AU - Leder, Lennart AU - Skopalik, Alexander ID - 112 T2 - Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC) TI - Congestion Games with Complementarities 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 - Polevoy, Gleb AU - Trajanovski, Stojan AU - Grosso, Paola AU - de Laat, Cees ID - 17652 KW - flow KW - filter KW - MMSA KW - set cover KW - approximation KW - local ratio algorithm SN - 978-3-319-71150-8 T2 - Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I TI - Filtering Undesirable Flows in Networks ER - TY - CONF AU - Polevoy, Gleb AU - de Weerdt, M.M. ID - 17653 KW - interaction KW - reciprocation KW - contribute KW - shared effort KW - curbing KW - convergence KW - threshold KW - Nash equilibrium KW - social welfare KW - efficiency KW - price of anarchy KW - price of stability T2 - Proceedings of the 29th Benelux Conference on Artificial Intelligence TI - Reciprocation Effort Games ER - TY - CONF AU - Polevoy, Gleb AU - de Weerdt, M.M. ID - 17654 KW - agents KW - projects KW - contribute KW - shared effort game KW - competition KW - quota KW - threshold KW - Nash equilibrium KW - social welfare KW - efficiency KW - price of anarchy KW - price of stability T2 - Proceedings of the 29th Benelux Conference on Artificial Intelligence TI - Competition between Cooperative Projects ER - TY - GEN AB - 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. AU - Fischer, Matthias AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ID - 17811 T2 - arXiv:1702.03400 TI - Gathering Anonymous, Oblivious Robots on a Grid 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 - CONF AB - 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. AU - Abu-Khzam, Faisal N. AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Podlipyan, Pavel ID - 82 T2 - Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW) TI - Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity ER - TY - CONF AB - 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). AU - Kling, Peter AU - Mäcker, Alexander AU - Riechers, Sören AU - Skopalik, Alexander ID - 59 T2 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) TI - Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource ER - TY - CONF AU - Feldkord, Björn AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm ID - 70 T2 - Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA) TI - Price Fluctuations in Online Leasing ER - TY - THES AU - Podlipyan, Pavel ID - 703 TI - Local Algorithms for the Continuous Gathering Problem ER - TY - THES AU - Riechers, Sören ID - 704 TI - Scheduling with Scarce Resources ER - TY - JOUR AU - Mäcker, Alexander AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ID - 706 IS - 4 JF - Journal of Combinatorial Optimization TI - Cost-efficient Scheduling on Machines from the Cloud VL - 36 ER -