@inproceedings{d6587ae882dd44b2b21eccfd1dd06112,
title = "An O(f) Bi-approximation for Weighted Capacitated Covering with Hard Capacity",
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 - ε), 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.",
keywords = "Bi-approximation, Capacitated covering with hard capacity, Partial cover",
author = "Tu, {Hai Lun} and Kao, {Mong Jen} and Lee, {D. T.}",
note = "Publisher Copyright: {\textcopyright} Springer Nature Singapore Pte Ltd. 2019.; 23rd International Computer Symposium, ICS 2018 ; Conference date: 20-12-2018 Through 22-12-2018",
year = "2019",
doi = "10.1007/978-981-13-9190-3_51",
language = "English",
isbn = "9789811391897",
series = "Communications in Computer and Information Science",
publisher = "Springer Verlag",
pages = "468--475",
editor = "Chuan-Yu Chang and Chien-Chou Lin and Horng-Horng Lin",
booktitle = "New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers",
address = "德國",
}