An O(f) Bi-approximation for Weighted Capacitated Covering with Hard Capacity

Hai Lun Tu*, Mong Jen Kao, D. T. Lee

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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 - ε), we have an O(1/ε)f -approximation algorithm. This gives a parametric trade-off between the total demand to be covered and the cost of the resulting demand assignment.

Original languageEnglish
Title of host publicationNew Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers
EditorsChuan-Yu Chang, Chien-Chou Lin, Horng-Horng Lin
PublisherSpringer Verlag
Number of pages8
ISBN (Print)9789811391897
StatePublished - 2019
Event23rd International Computer Symposium, ICS 2018 - Yunlin, Taiwan
Duration: 20 Dec 201822 Dec 2018

Publication series

NameCommunications in Computer and Information Science
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937


Conference23rd International Computer Symposium, ICS 2018


  • Bi-approximation
  • Capacitated covering with hard capacity
  • Partial cover


Dive into the research topics of 'An O(f) Bi-approximation for Weighted Capacitated Covering with Hard Capacity'. Together they form a unique fingerprint.

Cite this