IMPROVED CONSTANT-TIME APPROXIMATION ALGORITHMS FOR MAXIMUM MATCHINGS AND OTHER OPTIMIZATION PROBLEMS.

We study constant-time approximation algorithms for bounded-degree graphs, which run in time independent of the number of vertices n. We present an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity O (d²), where d is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error ∈n 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/∈. Our approximation algorithm for the maximum matching problem can be transformed to a two-sided error tester for the property of having a perfect matching. On the contrary, we show that every one-sided error tester for the property requires at least Ω(n)queries. [ABSTRACT FROM AUTHOR]