The Price of Being Near-Sighted

Achieving a global goal based on local information is challenging, especially in complex and large-scale networks such as the Internet or even the human brain. In this paper, we provide an almost tight classification of the possible tradeoff between the amount of local information and the quality of the global solution for general covering and packing problems. Specifically, we give a distributed algorithm using only small messages which obtains an (½¢)1/k-approximation for general covering and packing problems in time O(k2), where ½ depends on the LP’s coefficients. If message size is unbounded, we present a second algorithm that achieves an O(n1/k) approximation in O(k) rounds. Finally, we prove that these algorithms are close to optimal by giving a lower bound on the approximability of packing problems given that each node has to base its decision on information from its k-neighborhood.