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

Thorsten Götte; Christina Kolb; Christian Scheideler; Julian Werthmann

doi:10.48550/arXiv.2107.14570

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

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

Research output: Working paper › Preprint › Academic

15 Downloads (Pure)

Abstract

We observe message-efficient distributed algorithms for the Set Cover problem. 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 Õ (log²(Δ))-time and O(√Δ)(n+m))-message algorithm with expected approximation ration of O(log(Δ)) in the KT₀ model. The value Δ denotes the maximal cardinality of each subset. Our algorithm is \emph{almost} optimal with regard to time and message complexity. Further, we present Set Cover algorithm in the Beeping model that only relies on carrier-sensing and can trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [PODC '03].

Original language	English
Publisher	ArXiv.org
Number of pages	16
DOIs	https://doi.org/10.48550/arXiv.2107.14570
Publication status	Published - 2021
Externally published	Yes

Access to Document

10.48550/arXiv.2107.14570

ArticleFinal published version, 822 KB

1 Conference contribution
1 Article

Beep-and-Sleep: Message and Energy Efficient Set Cover
Götte, T., Kolb, C., Scheideler, C. & Werthmann, J., 16 Mar 2023, In: Theoretical computer science. 950, 113756.
Research output: Contribution to journal › Article › Academic › peer-review
1 Citation (Scopus)
Beep-And-Sleep: Message and Energy Efficient Set Cover
Götte, T., Kolb, C., Scheideler, C. & Werthmann, J., 2021, Algorithms for Sensor Systems: 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2021, Lisbon, Portugal, September 9–10, 2021, Proceedings. Gasieniec, L., Klasing, R. & Radzik, T. (eds.). Cham: Springer, p. 94-110 17 p. (Lecture Notes in Computer Science; vol. 12961).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
1 Citation (Scopus)

Cite this

@techreport{4869fe321b2f4a8b8bb6073d75517730,

title = "Beep-And-Sleep: Message and Energy Efficient Set Cover",

abstract = "We observe message-efficient distributed algorithms for the Set Cover problem. 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 {\~O} (log2(Δ))-time and O(√Δ)(n+m))-message algorithm with expected approximation ration of O(log(Δ)) in the KT0 model. The value Δ denotes the maximal cardinality of each subset. Our algorithm is \emph{almost} optimal with regard to time and message complexity. Further, we present Set Cover algorithm in the Beeping model that only relies on carrier-sensing and can trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [PODC '03].",

author = "Thorsten G{\"o}tte and Christina Kolb and Christian Scheideler and Julian Werthmann",

year = "2021",

doi = "10.48550/arXiv.2107.14570",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

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

AU - Götte, Thorsten

AU - Kolb, Christina

AU - Scheideler, Christian

AU - Werthmann, Julian

PY - 2021

Y1 - 2021

N2 - We observe message-efficient distributed algorithms for the Set Cover problem. 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 Õ (log2(Δ))-time and O(√Δ)(n+m))-message algorithm with expected approximation ration of O(log(Δ)) in the KT0 model. The value Δ denotes the maximal cardinality of each subset. Our algorithm is \emph{almost} optimal with regard to time and message complexity. Further, we present Set Cover algorithm in the Beeping model that only relies on carrier-sensing and can trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [PODC '03].

AB - We observe message-efficient distributed algorithms for the Set Cover problem. 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 Õ (log2(Δ))-time and O(√Δ)(n+m))-message algorithm with expected approximation ration of O(log(Δ)) in the KT0 model. The value Δ denotes the maximal cardinality of each subset. Our algorithm is \emph{almost} optimal with regard to time and message complexity. Further, we present Set Cover algorithm in the Beeping model that only relies on carrier-sensing and can trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [PODC '03].

U2 - 10.48550/arXiv.2107.14570

DO - 10.48550/arXiv.2107.14570

M3 - Preprint

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

PB - ArXiv.org

ER -

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

Abstract

Access to Document

Fingerprint

Research output

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

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

Cite this