Distributed Approximation of Capacitated Dominating Sets

We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various distributed network applications. Given a network graph G=(V,E), and a capacity cap(v)aa"center dot for each node vaV, the CapMDS problem asks for a subset SaS dagger V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S, and every node vaS covers at most cap(v) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local, i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time complexity that essentially grows linearly with the network diameter. On the other hand, if for some parameter epsilon > 0, capacities can be violated by a factor of 1+epsilon, CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding technique, we present a distributed bi-criteria algorithm that achieves an O(log I")-approximation in time O(log (3) n+log (n)/epsilon), where n and Delta denote the number of nodes and the maximal degree in G, respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem can be approximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local.