Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The design of distributed approximation protocols is a relatively new rapidly developing area of research. However, so far little progress was done in the study of the hardness of distributed approximation. In this paper we initiate the systematic study of this subject, and show strong unconditional lower bounds on the time-approximation tradeoff of the distributed minimum spanning tree problem, and some of its variants.

REFERENCES

• 1: B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States [doi>10.1145/28395.28421]
• 2: B. Awerbuch, A. Goldberg, M. Luby and S. Plotkin, Network decomposition and locality in distributed computation. in Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 364--369, 1989.
• 3: Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 4: Andrzej Czygrinow , M. Handckowiak , Michal Karonski, Distributed O(Delta log(n))-Edge-Coloring Algorithm, Proceedings of the 9th Annual European Symposium on Algorithms, p.345-355, August 28-31, 2001
• 5: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 6: Amit Chakrabarti , Bernard Chazelle , Benjamin Gum , Alexey Lvov, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.305-311, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301325]
• 7: A. Czygrinow, M. Hanckowiak, E. Szymanska, Distributed Algorithm for Approximating the Maximum Matching, manuscript.
• 8: F. Chin and H. F. Ting, An almost linear time and O(n log n + e) messages distributed algorithm for minimum-weight spanning trees, in Proc. 26th IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA, 1985, pp. 257--266.
• 9: Devdatt Dubhashi , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan , Arvind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: Devdatt P. Dubhashi , Alessandro Panconesi, Near-Optimal Distributed Edge Coloring, Proceedings of the Third Annual European Symposium on Algorithms, p.448-459, September 25-27, 1995
• 11: Michael Elkin, A faster distributed protocol for constructing a minimum spanning tree, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 12: Lars Engebretsen , Jonas Holmerin, Clique Is Hard to Approximate within n1-o(1), Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.2-12, July 09-15, 2000
• 13: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 14: Juan A. Garay , Shay Kutten , David Peleg, A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees, SIAM Journal on Computing, v.27 n.1, p.302-316, Feb. 1998 [doi>10.1137/S0097539794261118]
• 15: O. Goldreich , S. Goldwasser , D. Ron, Property testing and its connection to learning and approximation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.339, October 14-16, 1996
• 16: Eli Gafni, Improvements in the time complexity of two message-optimal election algorithms, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.175-185, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323612]
• 17: David A. Grable , Alessandro Panconesi, Nearly optimal distributed edge coloring in O(log log n) rounds, Random Structures & Algorithms, v.10 n.3, p.385-405, May 1997 [doi>10.1002/(SICI)1098-2418(199705)10:3<385::AID-RSA6>3.0.CO;2-S]
• 18: L. Jia, R. Rajaraman, and R. Suel, An Efficient Distributed Algorithm for Constructing Small Dominating Sets, In Proc. of the 20th ACM Symp. on Principles of Distributed Computing, pp. 33--42, 2001.
• 19: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 20: Shay Kutten , David Peleg, Fast distributed construction of small k-dominating sets and applications, Journal of Algorithms, v.28 n.1, p.40-66, July 1, 1998 [doi>10.1006/jagm.1998.0929]
• 21: Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872040]
• 22: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 23: Zvi Lotker , Boaz Patt-Shamir , David Peleg, Distributed MST for constant diameter graphs, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.63-71, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383984]
• 24: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 25: David Peleg , Vitaly Rubinovich, A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.253, October 17-18, 1999
• 26: Alessandro Panconesi , Aravind Srinivasan, Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds, SIAM Journal on Computing, v.26 n.2, p.350-368, April 1997 [doi>10.1137/S0097539793250767]
• 27: D. Peleg and A. Schaffer, Graph Spanners, Journal of Graph Theory 13 (1989), 99--116.
• 28: David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, SIAM Journal on Computing, v.18 n.4, p.740-747, Aug. 1989 [doi>10.1137/0218050]
• 29: V. Rubinovich, Distributed minimum spanning tree construction. M. Sc. Thesis, Bar-Ilan University, Ramat-Gan, Israel, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Theory

Keywords:
hardness of approximation, minimum spanning tree