Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems

Abstract

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^2)$, where $d$ is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error $\epsilon 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 $\frac{1}{\epsilon}$. 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 $\Omega(n)$ queries.