Distributed approximation
Author:
Open Access
- 1 December 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 35 (4) , 40-57
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.Keywords
This publication has 12 references indexed in Scilit:
- Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models2004
- A Fast Distributed Algorithm for Approximating the Maximum Matching2004
- Computing almost shortest paths2001
- Approximating Fractional Multicommodity Flow Independent of the Number of CommoditiesSIAM Journal on Discrete Mathematics, 2000
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding BoundsSIAM Journal on Computing, 1997
- Explicit construction of graphs with an arbitrary large girth and of large sizeDiscrete Applied Mathematics, 1995
- A parallel approximation algorithm for positive linear programming1993
- Linear programming without the matrix1993
- Locality in Distributed Graph AlgorithmsSIAM Journal on Computing, 1992
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974