The Price of Being Near-sighted
Fabian Kühn, Thomas Moscibroda, Roger P. Wattenhofer · 2006
Achieving a global goal based on local information is chal-lenging, especially in complex and large-scale networks such as the Internet or even the human brain. In this pa-per, we provide an almost tight classification of the possible trade-off between the amount of local informationand the quality of the global solution for general covering and packing problems. Specifically, we give a dis-tributed algorithm using only small messages which obtains an (ae\\Delta)1/k-approximation for general covering andpacking problems in time O( k2), where ae depends on theLP's coefficients. If message size is unbounded, we present a second algorithm that achieves an O(n1/k) approxima-tion in O( k) rounds. Finally, we prove that these algo-rithms are close to optimal by giving a lower bound on the approximability of packing problems given that eachnode has to base its decision on information from its k-neighborhood.