有多重限制之點覆蓋集近似演算法

An Approximation Algorithm for Vertex Cover with Multiple Covering Constraints

洪恩平(Eunpyeong Hong)

指導教授 ： 李德財

共同指導教授 ： 高孟駿

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201900977

摘要

無資料

關鍵字

點覆蓋集問題 ； 多重覆蓋限制 ； 近似演算法

並列摘要

We consider the vertex cover problem with multiple covering constraints (VC-MCC), which is a generalization of the vertex cover problem. In this problem, a hypergraph $G=(V,E)$ is given as an input with a maximum edge size $f$, a cost function $w: V
ightarrow mathbb{Z}^+$, and edge subsets $P_1,P_2,ldots,P_r$ of $E$ along with covering requirements $k_1,k_2, ldots,k_r$
for each subset. The objective is to find a minimum cost subset $S$ of $V$ such that, for each edge subset $P_i$, at least $k_i$ edges of it are covered by $S$. This problem is a basic yet general form of the classical vertex cover problem and a generalization of the edge-partitioned vertex cover problem considered by Bera et al.

We present a primal-dual algorithm which yields an $left(f cdot H_r + H_r
ight)$-approximation for this problem where $H_r$ is the $r^{th}$ harmonic number. This improves over the previous ratio of $(3cflog r)$ due to Bera et al., where $c$ is a large constant used to ensure a low failure probability for Monte-Carlo randomized algorithms. Compared to the previous result, the proposed algorithm is deterministic and purely combinatorial, which means that no Ellipsoid solver is required for this basic problem. Our result can be seen as a novel reinterpretation of a few classical tight results using the language of LP primal-duality.

並列關鍵字

Vertex Cover ； Multiple Covering Constraints ； Approximation Algorithm

參考文獻

[1] R Bar-Yehuda. Using homogeneous weights for approximating the partial cover problem. J. Algorithms, 39(2):137–144, May 2001.

[2] R Bar-Yehuda and S Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2):198 – 203, 1981.

[3] R Bar-Yehuda and S Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2):198 – 203, 1981.

[4] Suman K. Bera, Shalmoli Gupta, Amit Kumar, and Sambuddha Roy. Approximation algorithms for the partition vertex cover problem. Theoretical Computer Science, 555:2 – 8, 2014. Special Issue on Algorithms and Computation.

[5] Nader H. Bshouty and Lynn Burroughs. Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pages 298–308. Springer, 1998.