Tight approximation for partial vertex cover with hard capacities

Mong Jen Kao*, Jia Yau Shiau, Ching Chi Lin, D. T. Lee

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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+ϵ) 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.

Original languageEnglish
Pages (from-to)61-72
Number of pages12
JournalTheoretical Computer Science
Volume778
DOIs
StatePublished - 26 Jul 2019

Keywords

  • Approximation algorithm
  • Capacitated cover
  • Hard capacity
  • Partial cover

Fingerprint

Dive into the research topics of 'Tight approximation for partial vertex cover with hard capacities'. Together they form a unique fingerprint.

Cite this