Please use this identifier to cite or link to this item:
|Title: ||Tight Approximation for Partial Vertex Cover with Hard Capacities|
|Authors: ||Jia-Yau Shiau|
|Keywords: ||Approximation Algorithm|
Capacitated Vertex Cover
|Issue Date: ||2018-12-21T02:45:09Z
|Publisher: ||Theoretical Computer Science|
|Abstract: ||Abstract: 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 paper we present an f-approximation for this problem, improving over a previous
result of (2f + 2)(1 + ) 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.
|Appears in Collections:||[資訊工程學系] 期刊論文|
Files in This Item:
All items in NTOUR are protected by copyright, with all rights reserved.