Distributed approximation: a survey

ABSTRACT

Recently considerable progress was achieved in designing efficient distributed approximation algorithms, and in demonstrating hardness of distributed approximation for various problems. In this survey we overview the research in this area and propose several directions for future research.

REFERENCES

• 1: Yair Bartal , John W. Byers , Danny Raz, Global Optimization Using Local Information with Applications to Flow Control, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.303, October 19-22, 1997
• 2: 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
• 3: A. Czygrinow, M. Hanckowiak, and E. Szymanska. Distributed algorithm for approximating the maximum matching, manuscript. 2003.
• 4: 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
• 5: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 6: D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, and A. Srinivisan. Fast distributed algorithm for (weakly) connected dominating sets and linear-size skeletons, 2003.
• 7: Friedrich Eisenbrand , Stefan Funke , Naveen Garg , Jochen Könemann, A combinatorial algorithm for computing a maximum independent set in a t-perfect graph, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: Michael Elkin, Computing almost shortest paths, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.53-62, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383983]
• 9: Michael Elkin, Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007407]
• 10: Michael Elkin , Jian Zhang, Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011791]
• 11: Lisa K. Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics, v.13 n.4, p.505-520, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480199355754]
• 12: Lisa Fleischer, A fast approximation scheme for fractional covering problems with variable upper bounds, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 13: R. G. Gallager. A shortest path routing algorithm with automatic resynch. Technical Report LIDS-P-1175, 1976.
• 14: 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]
• 15: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 16: 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 Distrib. Comput. (PODC), pages 33--42, 2001.
• 17: F. Kuhn, T. Moscibroda, and R. Wattenhofer. Lower and upper bounds for distributed packing and covering. Technical Report 443, Dept. of Computer Science, ETH, Zurich, 2004.
• 18: F. Kuhn, T. Moscibroda, and R. Wattenhofer. What cannot be computed locally! Technical Report 438, Dept. of Computer Science, ETH, Zurich, 2004.
• 19: 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]
• 20: F. Kuhn and R. Wattenhofer. Distributed combinatorial optimization. Technical Report 426, Dept. of Computer Science, ETH, Zurich, 2004.
• 21: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 22: Felix Lazebnik , Vasiliy A. Ustimenko, Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Applied Mathematics, v.60 n.1-3, p.275-284, June 23, 1995 [doi>10.1016/0166-218X(94)00058-L]
• 23: G. LeLann. Distributed systems, towards a formal approach. In IFIP Congress, pages 155--160, 1977.
• 24: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 25: Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167211]
• 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: Christos H. Papadimitriou , Mihalis Yannakakis, Linear programming without the matrix, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.121-129, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167127]
• 28: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 29: 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
• 30: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 31: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 32: M. Wattenhofer and R. Wattenhofer. Distributed weighted matching. Technical Report 420, ETH, Zurich, Department of Computer Science, 2003.
• 33: A. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. 17th IEEE Symp. on Foundations of Computer Science, pages 222--227, 1977.