Lower and Upper Bounds for Distributed Packing and Covering
Fabian Kühn, Thomas Moscibroda, Roger P. Wattenhofer · Repository for Publications and Research Data (ETH Zurich) · 2004
Abstract We make a step towards understanding the distributed complexity of global optimization problems.We give bounds on the trade-off between locality and achievable approximation ratio of distributed algorithms for packing and covering problems. Extending a result of [9], we show that in k communi-cation rounds, maximum matching and therefore packing problems cannot be approximated better than \\Omega (nc/k 2/k) and \\Omega (\\Delta 1/k/k) where c is a small constant and n and \\Delta denote the number of nodes and the maximum degree of the network graph, respectively. This means that in order to obtain a constant or poly-logarithmic approximation, there are graphs with n nodes and graphs with maximum degree \\Delta on which\\Omega (plog n / log log n) and \\Omega (log \\Delta / log log \\Delta) rounds are needed, respectively. On the positive side, weprove that maximum matching and minimum vertex cover (the dual problem) can be approximated by O(\\Delta 1/k) in O(k) rounds, showing that the given lower bound is almost tight. We also give a distributedalgorithm which approximates any packing or covering LP by O( n1/k) in O(k) rounds. 1 Introduction Computing a global objective based on local information only lies at the heart of distributed computing theory.In this paper we present the first lower bounds for distributed packing problems such as maximum matching. In addition we exhibit new algorithms for packing (and also covering) problems which almost match thelower bounds.