有容量的點覆蓋問題在放寬條件下之可近似性

The Approximability of Capacitated Vertex Cover Problem with Relaxed Constraints

杜海倫(Hai-Lun Tu)

指導教授 ： 李德財

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

https://doi.org/10.6342/NTU201801682

摘要

無資料

關鍵字

有容量的點覆蓋問題 ； 硬容量 ； 主對偶架構 ； 部分覆蓋 ； 增加容量覆蓋

並列摘要

In this dissertation, we aim to address the approximability of the capacitated vertex cover (CVC) problem, i.e., a generic demand-to-service assignment model of the classical vertex cover problem, when certain constraints of interest are relaxed. In CVC, we are given a hypergraph H = (V, E) with a maximum edge size f. Each (hyper)edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset, or cover, such that the demands of the edges can be met by the capacities of the vertices and the multiplicity of each vertex does not exceed its available multiplicity. Depending on whether the available multiplicity of each vertex is limited, the work on CVC falls mainly in two categories: (1) soft capacity (SCVC), where the multiplicity of each vertex is unlimited, and (2) hard capacity (HCVC), where the available multiplicity of each vertex is limited.
We give an overview of the proposed models and methods for CVC, and summarize related research works for SCVC, HCVC and other variations in recent years. And our main results are focused on different relaxed constraint models of HCVC. When each vertex is unweighted, we have a (δ + 2)-approximation algorithm, where δ is the maximum vertex degree. For augmenting the available multiplicity by a factor of k ≥ 2, a cover with a cost ratio of (1 + 1/(k-1))(f − 1) to
the optimal cover for the original instance can be obtained. For partial cover, as the demand served is at least the ratio of (1 − ϵ), we have an O(1/ϵ)f-approximation algorithm for HCVC.

並列關鍵字

Capacitated Vertex Cover Problem ； Hard Capacity ； Primal-Dual Schema ； Partial Cover ； Augmented Cover

參考文獻

[1] B. S. Baker. Approximation algorithms for np-complete problems on planar graphs. Journal of the ACM, 41(1):153–180, 1994.

[2] R. Bar-Yehuda. One for the price of two: a unified approach for approximating covering problems. Algorithmica, 27(2):131–144, Jun 2000.

[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] R. Bar-Yehuda, G. Flysher, J. Mestre, and D. Rawitz. Approximation of partial capacitated vertex cover. SIAM Journal on Discrete Mathematics, 24(4):1441–1469, 2010.

[5] W.-C. Cheung, M. X. Goemans, and S. C.-W. Wong. Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’14, pages 1714–1726, 2014.