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) ? N for each node v ? V , the CapMDS problem asks for a subset S ? V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S , and every node v ? S 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 ? > 0, capacities can be violated by a factor of 1 + ?, 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 ?)-approximation in time O(log 3 n + log( n )/?), where n and ? 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.
distributed approximation capacities dominating sets lp relaxation