Source author record

Till Knollmann

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility

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.

preprint2020arXiv

The Online Multi-Commodity Facility Location Problem

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'04) 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 $Ω(\sqrt{|S|}+\frac{\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(\sqrt{|S|}\cdot\log n)$ -competitive algorithm and a randomized $O(\sqrt{|S|}\cdot\frac{\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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.