Research output per year
Research output per year
Thorsten Götte*, Christina Kolb, Christian Scheideler, Julian Werthmann
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
We observe message- and energy-efficient distributed algorithms for the SetCover Problem in the KT0 and Beeping model. Given a ground set U of n elements and m subsets of U, we aim to find the minimal number of these subsets that contain all elements. In the default distributed setup of this problem, each set has a bidirected communication link with each element it contains. Our first result is a Õ (log2(Δ ) ) -time and Õ(Δ)(n+m)) -message algorithm with expected approximation ratio of O(log (Δ ) ) in the KT0 model. The value Δ denotes the maximum of each subset’s cardinality and the number of sets an element is contained in. Our algorithm is almost optimal concerning time and message complexity. Further, we present the first SetCover algorithm for general instances in the Beeping model. It computes an Õ(Δk) -approximation in time O(k3) for any parameter k> 3. Thus, it can trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [PODC’03].
Original language | English |
---|---|
Title of host publication | Algorithms for Sensor Systems |
Subtitle of host publication | 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021, Proceedings |
Editors | Leszek Gasieniec, Ralf Klasing, Tomasz Radzik |
Publisher | Springer |
Pages | 94-110 |
Number of pages | 17 |
Volume | 12961 |
Edition | 1 |
ISBN (Electronic) | 9783030892401 |
ISBN (Print) | 9783030892395 |
DOIs | |
Publication status | Published - 19 Oct 2021 |
Event | 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021 - Virtual, Online Duration: 9 Sept 2021 → 10 Sept 2021 |
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 12961 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021 |
---|---|
City | Virtual, Online |
Period | 9/09/21 → 10/09/21 |
Research output: Contribution to journal › Article › peer-review