A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
复制标题
用于近似最小顶点覆盖尺寸的近最优次线性时间算法
DOI：
10.1137/1.9781611973099.88
复制
发表时间：
2011
期刊：
影响因子：
1.1
通讯作者：
R. Rubinfeld
中科院分区：
文献类型：
--
作者：
Krzysztof Onak;D. Ron;M. Rosen;R. Rubinfeld
我们给出了一个几乎最佳的倍率算法，用于近似图G中的最小顶点覆盖物的大小。该算法可能会查询其选择的任何顶点V的度量（V），并且对于每个1≤i≤DEG（ v），它可能会要求v。让vcopt（g）的ITH邻居表示G中的顶点覆盖物的最小大小，算法输出，具有很高的恒定成功概率，估计值[等式]，其中[等式]，其中[等式]，其中e是一个给出的近似参数。吉田等人（STOC 2009）的最佳先前已知sublinear算法的顶点。 ω（d）（用于常数e）由于parnas和ron引起的（TCS 2007）获得了这种估计值（具有任何恒定的乘法因子），我们的结果几乎是最佳的。
在图形密度的情况下，即边的数量为θ（n2），我们考虑了另一个模型，其中算法可能会要求任何一对u和v，u和v是否有u之间的边缘v。我们展示了如何调整对该模型使用邻居查询的算法，并获得了输出A（2，e）的算法，该算法的最小顶点盖的大小的查询复杂性和运行时间为O（n） ·poly（1/e）。
We give a nearly optimal sublinear-time algorithm for approximating the size of a minimum vertex cover in a graph G. The algorithm may query the degree deg(v) of any vertex v of its choice, and for each 1 ≤ i ≤ deg(v), it may ask for the ith neighbor of v. Letting VCopt(G) denote the minimum size of vertex cover in G, the algorithm outputs, with high constant success probability, an estimate [EQUATION] such that [EQUATION], where e is a given additive approximation parameter. We refer to such an estimate as a (2, e)-estimate. The query complexity and running time of the algorithm are O([EQUATION] · poly(1/e)), where d denotes the average vertex degree in the graph. The best previously known sublinear algorithm, of Yoshida et al. (STOC 2009), has query complexity and running time O(d4/e2), where d is the maximum degree in the graph. Given the lower bound of Ω(d) (for constant e) for obtaining such an estimate (with any constant multiplicative factor) due to Parnas and Ron (TCS 2007), our result is nearly optimal.
In the case that the graph is dense, that is, the number of edges is Θ(n2), we consider another model, in which the algorithm may ask, for any pair of vertices u and v, whether there is an edge between u and v. We show how to adapt the algorithm that uses neighbor queries to this model and obtain an algorithm that outputs a (2, e)-estimate of the size of a minimum vertex cover whose query complexity and running time are O(n) · poly(1/e).