Tight approximation for partial vertex cover with hard capacities

作     者：Kao, Mong-Jen Shiau, Jia-Yau Lin, Ching-Chi Lee, D. T. 

作者机构：Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi Taiwan Natl Taiwan Univ Grad Inst Elect Engn Taipei Taiwan Natl Taiwan Ocean Univ Dept Comp Sci & Engn Keelung Taiwan Acad Sinica Inst Informat Sci Taipei Taiwan 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2019年第778卷

页      面：61-72页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Approximation algorithm Capacitated cover Partial cover Hard capacity 

摘      要：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 72. 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 72 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 paper we present an f-approximation for this problem, improving over a previous result of (2f + 2)(1 + epsilon) by Cheung et al. to the tight 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. (C) 2019 Elsevier B.V. All rights reserved.