TY - CONF AU - Bienkowski, Marcin AU - Feldkord, Björn AU - Schmidt, Pawel ID - 20817 T2 - Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS) TI - A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location ER - TY - JOUR AB - Over the past decades, the Gathering problem, which asks to gather a group of robots in finite time given some restrictions, has been intensively studied. In this paper, we are given a group of n autonomous, dimensionless, deterministic, and anonymous robots, with bounded viewing range. Assuming a continuous time model, the goal is to gather these robots into one point in finite time. We introduce a simple convergence criterion that defines a new class of algorithms which perform gathering in O(nd) time, where d is the diameter of the initial robot configuration. We show that some gathering algorithms in the literature belong to this class and propose two new algorithms that belong to this class and have quadratic running time, namely, Go-To-The-Relative-Center algorithm (GTRC) and Safe-Go-To-The-Relative-Center algorithm (S-GTRC). We prove that the latter can perform gathering without collision by using a slightly more complex robot model: non oblivious, chiral, and luminous (i.e. robots have observable external memory, as in [8]). We also consider a variant of the Gathering problem, the Near-Gathering problem, in which robots must get close to each other without colliding. We show that S-GTRC solves the Near-Gathering problem in quadratic time and assumes a weaker robot model than the one assumed in the current state-of-the-art. AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Podlipyan, Pavel ID - 22510 JF - Theoretical Computer Science KW - Local algorithms KW - Distributed algorithms KW - Collisionless gathering KW - Mobile robots KW - Multiagent system SN - 0304-3975 TI - A continuous strategy for collisionless gathering VL - 852 ER - TY - JOUR AB - In this paper, we reconsider the well-known discrete, round-based Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita [2] for gathering n autonomous mobile robots with limited viewing range in the plane. Remarquably, this algorithm exploits the fact that during its execution, many collisions of robots occur. Such collisions are interpreted as a success because it is assumed that such collided robots behave the same from now on. This is acceptable under the assumption that each robot is represented by a single point. Otherwise, collisions should be avoided. In this paper, we consider a continuous Go-To-The-Center algorithm in which the robots continuously observe the positions of their neighbors and adapt their speed (assuming a speed limit) and direction. Our first results are time bounds of O(n2) for gathering in two dimensions Euclidean space, and Θ(n) for the one dimension. Our main contribution is the introduction and evaluation of a continuous algorithm which performs Go-To-The-Center considering only the neighbors of a robot with respect to the Gabriel subgraph of the visibility graph, i.e. Go-To-The-Gabriel-Center algorithm. We show that this modification still correctly executes gathering in one and two dimensions, with the same time bounds as above. Simulations exhibit a severe difference of the behavior of the Go-To-The-Center and the Go-To-The-Gabriel-Center algorithms: Whereas lots of collisions occur during a run of the Go-To-The-Center algorithm, typically only one, namely the final collision occurs during a run of the Go-To-The-Gabriel-Center algorithm. We can prove this “collisionless property” of the Go-To-The-Gabriel-Center algorithm for one dimension. In two-dimensional Euclidean space, we conjecture that the “collisionless property” holds for almost every initial configuration. We support our conjecture with measurements obtained from the simulation where robots execute both continuous Go-To-The-Center and Go-To-The-Gabriel-Center algorithms. AU - Li, Shouwei AU - Meyer auf der Heide, Friedhelm AU - Podlipyan, Pavel ID - 22511 JF - Theoretical Computer Science KW - Local algorithms KW - Distributed algorithms KW - Collisionless gathering KW - Mobile robots KW - Multiagent system SN - 0304-3975 TI - The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots VL - 852 ER - TY - CONF AU - Castenow, Jannik AU - Götte, Thorsten AU - Knollmann, Till AU - Meyer auf der Heide, Friedhelm ED - Johnen, C. ED - Schiller, E.M. ED - Schmid, S. ID - 26986 T2 - Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021 TI - The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation VL - 13046 ER - TY - GEN AB - Consider a set of jobs connected to a directed acyclic task graph with a fixed source and sink. The edges of this graph model precedence constraints and the jobs have to be scheduled with respect to those. We introduce the Server Cloud Scheduling problem, in which the jobs have to be processed either on a single local machine or on one of many cloud machines. Both the source and the sink have to be scheduled on the local machine. For each job, processing times both on the server and in the cloud are given. Furthermore, for each edge in the task graph, a communication delay is included in the input and has to be taken into account if one of the two jobs is scheduled on the server, the other in the cloud. The server can process jobs sequentially, whereas the cloud can serve as many as needed in parallel, but induces costs. We consider both makespan and cost minimization. The main results are an FPTAS with respect for the makespan objective for a fairly general case and strong hardness for the case with unit processing times and delays. AU - Maack, Marten AU - Meyer auf der Heide, Friedhelm AU - Pukrop, Simon ID - 27778 T2 - arXiv:2108.02109 TI - Full Version -- Server Cloud Scheduling ER - TY - GEN AU - Berger, Thilo Frederik ID - 44234 TI - Combining Mobility, Heterogeneity, and Leasing Approaches for Online Resource Allocation ER - TY - GEN AU - Pranger, Sebastian ID - 44233 TI - Online k-Facility Reallocation using k-Server Algorithms ER - TY - CONF AB - Most existing robot formation problems seek a target formation of a certain minimal and, thus, efficient structure. Examples include the Gathering and the Chain-Formation problem. In this work, we study formation problems that try to reach a maximal structure, supporting for example an efficient coverage in exploration scenarios. A recent example is the NASA Shapeshifter project, which describes how the robots form a relay chain along which gathered data from extraterrestrial cave explorations may be sent to a home base. As a first step towards understanding such maximization tasks, we introduce and study the Max-Chain-Formation problem, where $n$ robots are ordered along a winding, potentially self-intersecting chain and must form a connected, straight line of maximal length connecting its two endpoints. We propose and analyze strategies in a discrete and in a continuous time model. In the discrete case, we give a complete analysis if all robots are initially collinear, showing that the worst-case time to reach an $\varepsilon$-approximation is upper bounded by $\mathcal{O}(n^2 \cdot \log (n/\varepsilon))$ and lower bounded by $\Omega(n^2 \cdot~\log (1/\varepsilon))$. If one endpoint of the chain remains stationary, this result can be extended to the non-collinear case. If both endpoints move, we identify a family of instances whose runtime is unbounded. For the continuous model, we give a strategy with an optimal runtime bound of $\Theta(n)$. Avoiding an unbounded runtime similar to the discrete case relies crucially on a counter-intuitive aspect of the strategy: slowing down the endpoints while all other robots move at full speed. Surprisingly, we can show that a similar trick does not work in the discrete model. AU - Castenow, Jannik AU - Kling, Peter AU - Knollmann, Till AU - Meyer auf der Heide, Friedhelm ED - Devismes , Stéphane ED - Mittal, Neeraj ID - 19899 SN - 978-3-030-64347-8 T2 - Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings TI - A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up VL - 12514 ER - TY - CONF AB - Let G = (V,E) be an undirected graph on n vertices with non-negative capacities on its edges. The mincut sensitivity problem for the insertion of an edge is defined as follows. Build a compact data structure for G and a given set S ⊆ V of vertices that, on receiving any edge (x,y) ∈ S×S of positive capacity as query input, can efficiently report the set of all pairs from S× S whose mincut value increases upon insertion of the edge (x,y) to G. The only result that exists for this problem is for a single pair of vertices (Picard and Queyranne, Mathematical Programming Study, 13 (1980), 8-16). We present the following results for the single source and the all-pairs versions of this problem. 1) Single source: Given any designated source vertex s, there exists a data structure of size 𝒪(|S|) that can output all those vertices from S whose mincut value to s increases upon insertion of any given edge. The time taken by the data structure to answer any query is 𝒪(|S|). 2) All-pairs: There exists an 𝒪(|S|²) size data structure that can output all those pairs of vertices from S× S whose mincut value gets increased upon insertion of any given edge. The time taken by the data structure to answer any query is 𝒪(k), where k is the number of pairs of vertices whose mincut increases. For both these versions, we also address the problem of reporting the values of the mincuts upon insertion of any given edge. To derive our results, we use interesting insights into the nearest and the farthest mincuts for a pair of vertices. In addition, a crucial result, that we establish and use in our data structures, is that there exists a directed acyclic graph of 𝒪(n) size that compactly stores the farthest mincuts from all vertices of V to a designated vertex s in the graph. We believe that this result is of independent interest, especially, because it also complements a previously existing result by Hariharan et al. (STOC 2007) that the nearest mincuts from all vertices of V to s is a laminar family, and hence, can be stored compactly in a tree of 𝒪(n) size. AU - Baswana, Surender AU - Gupta, Shiv AU - Knollmann, Till ED - Grandoni, Fabrizio ED - Herman, Grzegorz ED - Sanders, Peter ID - 20159 KW - Mincut KW - Sensitivity KW - Data Structure SN - 1868-8969 T2 - 28th Annual European Symposium on Algorithms (ESA 2020) TI - Mincut Sensitivity Data Structures for the Insertion of an Edge VL - 173 ER - TY - CONF AU - Castenow, Jannik AU - Harbig, Jonas AU - Jung, Daniel AU - Knollmann, Till AU - Meyer auf der Heide, Friedhelm ED - Devismes, Stéphane ED - Mittal, Neeraj ID - 20185 SN - 978-3-030-64347-8 T2 - Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings TI - Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented & Luminous Robots with Limited Visibility VL - 12514 ER -