Advertisement
Published in:
2019 | OriginalPaper | Chapter
An O(f) Bi-approximation for Weighted Capacitated Covering with Hard Capacity
Authors : Hai-Lun Tu, Mong-Jen Kao, D. T. Lee
Published in: New Trends in Computer Technologies and Applications
Publisher: Springer Singapore
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We consider capacitated vertex cover with hard capacity (HCVC) on f-hypergraphs. In this problem, we are given a hypergraph \(G=(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.
In this paper we present an O(f) bi-approximation for partial HCVC. As the demand served is at least the ratio of \((1-\epsilon )\), we have an \(O(1/\epsilon )f\)-approximation algorithm. This gives a parametric trade-off between the total demand to be covered and the cost of the resulting demand assignment.