We consider a swarm of $n$ robots in \mathbb{R}^d. The robots are oblivious, disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task gathering requires that all robots reach the same, not predefined position. In the related near-gathering task, they must reach distinct positions such that every robot sees the entire swarm. In the considered setting, gathering can be solved in $\mathcal{O}(n + Δ^2)$ synchronous rounds both in two and three dimensions, where $Δ$ denotes the initial maximal distance of two robots. In this work, we formalize a key property of efficient gathering protocols and use it to define $λ$-contracting protocols. Any such protocol gathers $n$ robots in the $d$-dimensional space in $\mathcal{O}(Δ^2)$ synchronous rounds. Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside of the local convex hulls of their neighborhoods -- $λ$-contracting protocols have this property -- requires $Ω(Δ^2)$ rounds to gather all robots. Among others, we prove that the $d$-dimensional generalization of the GtC-protocol is $λ$-contracting. Remarkably, our improved and generalized runtime bound is independent of $n$ and $d$. The independence of $d$ answers an open research question. We also introduce an approach to make any $λ$-contracting protocol collisionfree to solve near-gathering. The resulting protocols maintain the runtime of $Θ(Δ^2)$ and work even in the semi-synchronous model.

The famous k-Server Problem covers plenty of resource allocation scenarios, and several variations have been studied extensively for decades. However, to the best of our knowledge, no research has considered the problem if the servers are not identical and requests can express which specific servers should serve them. Therefore, we present a new model generalizing the k-Server Problem by preferences of the requests and proceed to study it in a uniform metric space for deterministic online algorithms (the special case of paging).

We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of a finite set (S) of commodities. Ravi and Sinha (SODA 2004) introduced the model as the Multi-Commodity Facility Location Problem (MFLP) and considered it an offline optimization problem. The model itself is similar to the FLP: i.e., requests are located at points of a finite metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances. In addition, requests and facilities are heterogeneous; they request or offer multiple commodities out of S. A request has to be connected to a set of facilities jointly offering the commodities demanded by it. In comparison to the FLP, an algorithm has to decide not only if and where to place facilities, but also which commodities to offer at each. To the best of our knowledge we are the first to study the problem in its online variant in which requests, their positions and their commodities are not known beforehand but revealed over time. We present results regarding the competitive ratio. On the one hand, we show that heterogeneity influences the competitive ratio by developing a lower bound on the competitive ratio for any randomized online algorithm of (Ω( √|S| + log/n log log n)) that already holds for simple line metrics. Here, (n) is the number of requests. On the other side, we establish a deterministic (O(√|S| · log n))-competitive algorithm and a randomized (O(√|S| · log/n log log n))-competitive algorithm. Further, we show that when considering a more special class of cost functions for the construction cost of a facility, the competitive ratio decreases given by our deterministic algorithm depending on the function.

Robot coordination problems deal with systems consisting of many autonomous, but simple, mobile agents that try to achieve a common, complex task. The agents' capabilities depend on the exact model and task but are typically very restricted. For example, there is usually no common coordinate system or sense of direction, and agents often have limited sensing capabilities. Among the most basic and well-studied type of tasks are GATHERING problems, in which initially scattered agents must gather at a single point. CHAINFORMATION problems represent another important formation primitive. Here, agents take the role of communication relays that, initially, form a winding chain connecting two base stations. The relays are to move such that the chain becomes straight, allowing for a more energy-efficient communication along the relay chain. Both GATHERING and CHAINFORMATION problems can be described as contracting: starting from an initially scattered formation, they seek to reach a smaller, more efficient structure. A natural complement are extension problems, where agents start in an initially dense formation and seek to reach an extended formation that covers as much area as possible. While there are some results about extension problems if agents move on grids or rings, results in standard discrete and continuous models for the Euclidean plane are scarce. Our work introduces the MAXFORM problem on the Euclidean plane and provides first analytical results for both the discrete and continuous case.

We present a new approach for competitive geometric routing in wireless ad hoc networks. We design a routing strategy that finds c-competitive paths for a positive constant c: i.e., paths which have a length at most c times the length of a shortest path. It is well-known that this cannot be achieved by online routing strategies which only consider the local neighborhood of a node for their routing decisions [17]. The main difficulty is uncovered regions within the wireless ad hoc network, which we denote as radio holes. Complex shapes of radio holes, for example zig-zag-shapes, make local geometric routing difficult: i.e., forwarded messages in direction to the destination might get stuck in a dead end or could be routed along very long detours. To be able to find c-competitive paths, additional knowledge about the position and shape of radio holes is needed. In order to gather the knowledge efficiently, we make use of a hybrid network approach. This approach assumes that we can not just make use of the ad hoc network but also of some cellular infrastructure, which is used to gather knowledge about the underlying ad hoc network. Communication via the cellular infrastructure incurs costs as cell phone providers are involved. Therefore, we use the cellular infrastructure only to compute routing paths in the ad hoc network. The actual data transmission takes place in the ad hoc network. To find good routing paths we aim at computing an abstraction of the ad hoc network in which radio holes are abstracted by bounding boxes. The advantage of bounding boxes as hole abstraction is that we only have to consider a constant number of nodes per hole. We prove that bounding boxes are a suitable hole abstraction that allows us to find c-competitive paths in the ad hoc network in the case of non-intersecting bounding boxes. In the case of intersecting bounding boxes, we show via simulations that our routing strategy significantly outperforms the so far best online routing strategies for wireless ad hoc networks. Finally, we also present a routing strategy that is c-competitive in the case of pairwise intersecting bounding boxes.

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 short 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 $\mathcalO łeft(łog ^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.