Improved distributed approximate matching

ABSTRACT

We present improved algorithms for finding approximately optimal matchings in both weighted and unweighted graphs. For unweighted graphs, we give an algorithm providing >(1-ε-approximation in O(log n) time for any constant ε > 0. This result improves on the classical 1 over 2-approximation due to Israeli and Itai. As a by-product, we also provide an improved algorithm for unweighted matchings in bipartite graphs. In the context of weighted graphs, we give another algorithm which provides (1 over 2-ε) approximation in general graphs in O(log n)time. The latter result improves on the known (1 over 4-ε-approximation in O(log n)time.

REFERENCES

• 1: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 2: N. Alon and J. H. Spencer. The Probabilistic Method, John Wiley and Sons, New York, 1992.
• 3: Thomas E. Anderson , Susan S. Owicki , James B. Saxe , Charles P. Thacker, High-speed switch scheduling for local-area networks, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.319-352, Nov. 1993 [doi>10.1145/161541.161736]
• 4: A. Czygrinow and M. Hakowiak. Distributed algorithm for better approximation of the maximum matching. Proceedings 9th Annual Int'l Conference on Computing and Combinatorics (COCOON), pages 242--251, 2003.
• 5: A. Czygrinow, M. Hańćkowiak and E. Szymańska. A fast distributed algorithm for approximating the maximum matching. In Proc. 12th Ann. European Symp. on Algorithms (ESA), pages 252--263, 2004.
• 6: Doratha E. Drake , Stefan Hougardy, A simple approximation algorithm for the weighted matching problem, Information Processing Letters, v.85 n.4, p.211-213, 28 February 2003 [doi>10.1016/S0020-0190(02)00393-9]
• 7: D. Drake and S. Hougardy. Improved linear time approximation algorithms for weighted matchings. Proc. 7th Int. Workshop on Randomization and ApproximationTechniques in Computer Science (APPROX), pp. 14--23, 2003.
• 8: Ted Fischer , Andrew V. Goldberg , David J. Haglin , Serge Plotkin, Approximating matchings in parallel, Information Processing Letters, v.46 n.3, p.115-118, June 11, 1993 [doi>10.1016/0020-0190(93)90055-E]
• 9: Michał Hańćkowiak , Michał Karoński , Alessandro Panconesi, A faster distributed algorithm for computing maximal matchings deterministically, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.219-228, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301360]
• 10: Nicholas J. A. Harvey, Algebraic Structures and Algorithms for Matching and Matroid Problems, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.531-542, October 21-24, 2006 [doi>10.1109/FOCS.2006.8]
• 11: J.-H. Hoepman.Simple distributed weighted matchings CoRR cs.DC/0410047, 2004.
• 12: J.-H. Hoepman, S. Kutten and Z. Lotker. Efficient distributed weighted matchings on trees. In Proc. SIROCCO 2006, pages 115--129.
• 13: J. E. Hopcroft and R. M. Karp. An N^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. on Computing, 2(4):225--231, 1973.
• 14: Stefan Hougardy , Doratha E. Vinkemeier, Approximating weighted matchings in parallel, Information Processing Letters, v.99 n.3, p.119-123, 16 August 2006 [doi>10.1016/j.ipl.2006.03.005]
• 15: Amos Israel , A. Itai, A fast and simple randomized parallel algorithm for maximal matching, Information Processing Letters, v.22 n.2, p.77-80, 1986 [doi>10.1016/0020-0190(86)90144-4]
• 16: R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.22-32, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22148]
• 17: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, The price of being near-sighted, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.980-989, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109666]
• 18: Zvi Lotker , Boaz Patt-Shamir , Adi Rosen, Distributed approximate matching, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281126]
• 19: L. Lovász and M. D. Plummer, Matching Theory. North Holland, 1986.
• 20: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 21: Marcin Mucha , Piotr Sankowski, Maximum Matchings via Gaussian Elimination, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.248-255, October 17-19, 2004 [doi>10.1109/FOCS.2004.40]
• 22: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 23: Nick McKeown, The iSLIP scheduling algorithm for input-queued switches, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.188-201, April 1999 [doi>10.1109/90.769767]
• 24: Seth Pettie , Peter Sanders, A simpler linear time 2/3 - ε approximation for maximum weight matching, Information Processing Letters, v.91 n.6, p.271-276, 30 September 2004 [doi>10.1016/j.ipl.2004.05.007]
• 25: R. Preis. Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In Proc. 16th Ann. Symp. on Theoretical Aspects of Computer Science (STACS), LNCS 1563, 259--269, 1999.
• 26: M. Wattenhofer and R. Wattenhofer. Distributed weighted matching. In Proc. 18th International Conference on Distributed Computing (DISC), pages 335--348, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
matching