摘要: Achieving a global goal based on local information is challenging, especially in complex and large-scale networks such as the Internet or even human brain. In this paper, we provide an almost tight classification of possible trade-off between amount quality solution for general covering packing problems. Specifically, give distributed algorithm using only small messages which obtains (ρΔ)1/k-approximation problems time O(k2), where ρ depends LP's coefficients. If message size unbounded, present second that achieves O(n1/k) approximation O(k) rounds. Finally, prove these algorithms are close to optimal by giving lower bound approximability given each node has base its decision from k-neighborhood.
acm.org
core.ac.uk
usi.ch参考文章(27)
David Peleg, Distributed Computing: A Locality-Sensitive Approach ,(1987)
Noga Alon, László Babai, Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem Journal of Algorithms. ,vol. 7, pp. 567- 583 ,(1985) , 10.1016/0196-6774(86)90019-2
Amos Israeli, A. Itai, A fast and simple randomized parallel algorithm for maximal matching Information Processing Letters. ,vol. 22, pp. 77- 80 ,(1986) , 10.1016/0020-0190(86)90144-4
Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, David Peleg, MST construction in O(log log n) communication rounds acm symposium on parallel algorithms and architectures. pp. 94- 100 ,(2003) , 10.1145/777412.777428
Sridhar Rajagopalan, Vijay V. Vazirani, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs SIAM Journal on Computing. ,vol. 28, pp. 525- 540 ,(1998) , 10.1137/S0097539793260763
Nathan Linial, Michael Saks, Low diameter graph decompositions Combinatorica. ,vol. 13, pp. 441- 454 ,(1993) , 10.1007/BF01303516
Neal E. Young, Randomized rounding without solving the linear program symposium on discrete algorithms. pp. 170- 178 ,(1995) , 10.5555/313651.313689
Felix Lazebnik, Vasiliy A. Ustimenko, Explicit construction of graphs with an arbitrary large girth and of large size Discrete Applied Mathematics. ,vol. 60, pp. 275- 284 ,(1995) , 10.1016/0166-218X(94)00058-L
Moni Naor, Larry Stockmeyer, What Can be Computed Locally? SIAM Journal on Computing. ,vol. 24, pp. 1259- 1277 ,(1995) , 10.1137/S0097539793254571
Christos H. Papadimitriou, Mihalis Yannakakis, Linear programming without the matrix Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. pp. 121- 129 ,(1993) , 10.1145/167088.167127