An improved constant-time approximation algorithm for maximum~matchings

ABSTRACT

This paper studies approximation algorithms for problems on degree-bounded graphs. Let n and d be the number of vertices and the degree bound, respectively. This paper presents an algorithm to approximate the size of some maximal independent set with additive error ε n whose running time is O(d²). Using this algorithm, it also shows that there are approximation algorithms for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to d and 1/ε. Its approximation algorithm for the maximum matching problem can be transformed to a testing algorithm for the property of having a perfect matching with two-sided error. On the contrary, it also shows that every one-sided error tester for the property requires at least Ω(n) queries.

REFERENCES

• 1: Jonathan Aronson , Martin Dyer , Alan Frieze , Stephen Suen, Randomized greedy matching. II, Random Structures & Algorithms, v.6 n.1, p.55-73, Jan. 1995 [doi>10.1002/rsa.3240060107]
• 2: Armen S. Asratian , Tristan M. J. Denley , Roland Häggkvist, Bipartite graphs and their applications, Cambridge University Press, New York, NY, 1998
• 3: A. Czumaj and C. Sohler. Sublinear-time algorithms. Bulletin of the EATCS, 89:23--47, 2006.
• 4: Martin Dyer and Alan Frieze. Randomized greedy matching. Random Struct. Algorithms, 2(1):29--45, 1991.
• 5: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: Oded Goldreich. Combinatorial property testing -- a survey. In In: Randomization Methods in Algorithm Design, pages 45--60. American Mathematical Society, 1998.
• 8: Oded Goldreich , Dana Ron, Property testing in bounded degree graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.406-415, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258627]
• 9: Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301366]
• 10: Ravi Kumar , Ronitt Rubinfeld, Algorithms column: sublinear time algorithms, ACM SIGACT News, v.34 n.4, December 2003 [doi>10.1145/954092.954103]
• 11: László Lovász. On the ratio of optimal integral and fractional covers. SIAM J. Discret. Math., 13:383--390, 1975.
• 12: Sharon Marko and Dana Ron. Distance approximation in bounded-degree and general sparse graphs. APPROX-RANDOM, pages 475--486, 2006.
• 13: Huy N. Nguyen , Krzysztof Onak, Constant-Time Approximation Algorithms via Local Improvements, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.327-336, October 25-28, 2008 [doi>10.1109/FOCS.2008.81]
• 14: Michal Parnas , Dana Ron, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Theoretical Computer Science, v.381 n.1-3, p.183-196, August, 2007 [doi>10.1016/j.tcs.2007.04.040]
• 15: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms

Keywords:
constant-time approximation algorithms, maximum matching, minimum set cover, minimum vertex cover, property testing