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

This article considers message and energy-efficient distributed algorithms for the SetCover Problem. Given a ground set U of n elements and a set S of 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. This results in a communication graph with n + m nodes and degree ∆. The value ∆ denotes the maximal degree of the communication graph, i.e., the maximum of all subsets’ sizes and the maximum number of sets an element is contained in.

We present SetCover algorithm in the Beeping model that only relies on carrier-sensing. In each synchronous time step, a node can either listen to the channel or beep. A listening node learns if one or more of its neighbors beeped or if none of its neighbors beeped. In particular, it neither learns which neighbors beeped nor how many neighbors beeped exactly. Given this model, we present an algorithm that runs in Ο(k³) time and has an expected approximation ratio of O(∆^3/k log² ∆). The value k ∈ [3, log ∆] is a parameter that lets us trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [14]. Our next result is a O(k²)-time and Õ(∆^{1/2 + 1/k} (n + m))-message algorithm (where Õ(·) hides polylogarithmic factors) with expected approximation ratio of O(∆^1/k log ∆) in the KT0-Congest model. In this variant of the well-known Congest model, time proceeds in synchronous rounds, and each node can send a distinct message of size O(log (n + m)) to each of its neighbors. Further, each node has a unique identifier of size O (log (n + m)). However, the crucial aspect of KT₀-Congest is that the nodes do not know their neighbors’ identifiers. Our algorithm is almost optimal concerning time and message complexity as we can show that there are hard instances that require Ω(∆^{1/2 −∈}m) messages for a constant approximation ratio.