Beep-And-Sleep: Message and Energy Efficient Set Cover

Thorsten Götte*, Christina Kolb, Christian Scheideler, Julian Werthmann

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 languageEnglish
Title of host publicationAlgorithms for Sensor Systems
Subtitle of host publication17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021, Proceedings
EditorsLeszek Gasieniec, Ralf Klasing, Tomasz Radzik
PublisherSpringer
Pages94-110
Number of pages17
Volume12961
Edition1
ISBN (Electronic)9783030892401
ISBN (Print)9783030892395
DOIs
Publication statusPublished - 19 Oct 2021
Event17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021 - Virtual, Online
Duration: 9 Sept 202110 Sept 2021

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12961 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021
CityVirtual, Online
Period9/09/2110/09/21

Fingerprint

Dive into the research topics of 'Beep-And-Sleep: Message and Energy Efficient Set Cover'. Together they form a unique fingerprint.

Cite this