An improved constant-time approximation algorithm for maximum~matchings
Authors:
Open Access
- 31 May 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 225-234
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(d2). 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.Keywords
This publication has 12 references indexed in Scilit:
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithmsTheoretical Computer Science, 2007
- Distance Approximation in Bounded-Degree and General Sparse Graphs2006
- Algorithms columnACM SIGACT News, 2003
- Sublinear time algorithms for metric space problems1999
- Combinatorial property testing (a survey)1998
- Property testing and its connection to learning and approximationJournal of the ACM, 1998
- Robust Characterizations of Polynomials with Applications to Program TestingSIAM Journal on Computing, 1996
- Randomized greedy matching. IIRandom Structures & Algorithms, 1995
- Randomized greedy matchingRandom Structures & Algorithms, 1991
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975