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

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

*此作品的通信作者

研究成果: Conference contribution同行評審

摘要

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.

原文English
主出版物標題New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers
編輯Chuan-Yu Chang, Chien-Chou Lin, Horng-Horng Lin
發行者Springer Verlag
頁面468-475
頁數8
ISBN(列印)9789811391897
DOIs
出版狀態Published - 2019
事件23rd International Computer Symposium, ICS 2018 - Yunlin, Taiwan
持續時間: 20 12月 201822 12月 2018

出版系列

名字Communications in Computer and Information Science
1013
ISSN(列印)1865-0929
ISSN(電子)1865-0937

Conference

Conference23rd International Computer Symposium, ICS 2018
國家/地區Taiwan
城市Yunlin
期間20/12/1822/12/18

指紋

深入研究「An O(f) Bi-approximation for Weighted Capacitated Covering with Hard Capacity」主題。共同形成了獨特的指紋。

引用此