- 學位論文
考慮嚴格容積的部分頂點覆蓋問題之最佳近似演算法
Tight Approximation for Partial Vertex Cover with Hard Capacities
摘要
這篇論文在超圖上討論考慮嚴格容積的部分頂點覆蓋問題。這個問題的輸入是一張超圖G=(V,E)、一個最大的多元邊大小f、以及一個最低的涵蓋要求R。除此之外，每一個多元邊都附帶一個需求參數；每一個節點都附帶一組參數：容積以及最大多重性。這個問題的目標是在不超過各個節點的容積下，找到涵蓋總和需求大於最低涵蓋要求的節點的多集合，並且在這個多集合中，每一個 節點都沒有超過它給定的最大多重性。 在這篇論文中，我們對超圖上考慮嚴格容積的部分頂點覆蓋問題提出了近似比率為f的近似演算法，相比於Cheung等人先前提出近似比率為(2f+2)(1+ϵ)的演算法，我們的演算法將近似比率逼到了可能的最佳近似比率。我們在這個問題中發現了兩個新的關鍵點，首先是參考先前相關研究的分析方法，對於原始線性規劃的端點(extreme point)做廣義的分析；第二個是我們對線性規劃的最佳解提出了一個強化的下界(lower-bound)。藉由這兩個新的關鍵點，我們得到近似比率為f的分析結果。
並列摘要
We consider the partial vertex cover problem with hard capacity constraints (Partial VC-HC) on hypergraphs. In this problem we are given a hypergraph G=(V,E) with a maximum edge size f and a covering requirement R. Each edge is associated with a demand, and each vertex is associated with a capacity and an (integral) available multiplicity. The objective is to compute a minimum vertex multiset such that at least R units of demand from the edges are covered by the capacities of the vertices in the multiset and the multiplicity of each vertex does not exceed its available multiplicity. In this thesis we present an f-approximation for this problem, improving over a previous result of (2f+2)(1+ϵ) by Cheung et al. to the tightest extent possible. Our new ingredient of this work is a generalized analysis on the extreme points of the natural LP, developed from previous works, and a strengthened LP lower-bound obtained for the optimal solutions.