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

文章基本信息

  • 标题:Tight Approximation for Partial Vertex Cover with Hard Capacities
  • 本地全文:下载
  • 作者:Jia-Yau Shiau ; Mong-Jen Kao ; Ching-Chi Lin
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2017
  • 卷号:92
  • 页码:64:1-64:13
  • DOI:10.4230/LIPIcs.ISAAC.2017.64
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We consider the partial vertex cover problem with hard capacity constraints (Partial VC-HC) on hypergraphs. In this problem we are given a hypergraph G=(V,E) with a maximum edge size f and a covering requirement R. Each edge is associated with a demand, and each vertex is associated with a capacity and an (integral) available multiplicity. The objective is to compute a minimum vertex multiset such that at least R units of demand from the edges are covered by the capacities of the vertices in the multiset and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an f-approximation for this problem, improving over a previous result of (2f+2)(1+epsilon) by Cheung et al to the tight extent possible. Our new ingredient of this work is a generalized analysis on the extreme points of the natural LP, developed from previous works, and a strengthened LP lower-bound obtained for the optimal solutions.
  • 关键词:Approximation Algorithm; Capacitated Vertex Cover; Hard Capacities
国家哲学社会科学文献中心版权所有