首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:O(f) Bi-Approximation for Capacitated Covering with Hard Capacities
  • 本地全文:下载
  • 作者:Mong-Jen Kao ; Hai-Lun Tu ; D. T. Lee
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2016
  • 卷号:64
  • 页码:40:1-40:12
  • DOI:10.4230/LIPIcs.ISAAC.2016.40
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph G = (V, E) with a maximum edge size f. Each 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 such that the demands of the edges can be covered 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 VC-HC that gives a trade-off on the number of augmented multiplicity and the cost of the resulting cover. In particular, we show that, by augmenting the available multiplicity by a factor of k geq 2, a cover with a cost ratio of (1+ frac{1}{k - 1})(f - 1) to the optimal cover for the original instance can be obtained. This improves over a previous result, which has a cost ratio of f^2 via augmenting the available multiplicity by a factor of f.
  • 关键词:Capacitated Covering; Hard Capacities; Bi-criteria Approximation
国家哲学社会科学文献中心版权所有