Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems
Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems
复制标题
DOI：
10.1137/110828691
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
Yuichi Yoshida;Masaki Yamamoto;Hiro Ito
中科院分区：
文献类型：
--
作者：
Yuichi Yoshida;Masaki Yamamoto;Hiro Ito
我们研究有界度图的常数时间近似算法，它在时间上与顶点数n无关。我们提出了一个算法，决定一个顶点是否包含在一个固定的最大独立集的预期查询复杂度为O（d^2）$，其中$d$是度界。利用这个算法，我们显示了常数时间近似算法与一定的乘法误差和加法误差$\n$的许多其他问题，例如，最大匹配问题、最小顶点覆盖问题和最小集合覆盖问题，这些问题在$d$和$\frac{1}{\displaystyle {\frac{1}$方面的运行速度比现有算法快。我们的近似算法的最大匹配问题可以转化为双边误差测试的性质，有一个完美的匹配。相反，我们表明，每个单侧错误测试的属性至少需要$\Omega（n）$查询。
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.