Name
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.tcs.2019.01.027 | Theoretical Computer Science |
Keywords | DocType | Volume |
Approximation algorithm,Capacitated cover,Partial cover,Hard capacity | Journal | 778 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mong-jen Kao | 1 | 26 | 7.82 |
| Jia-Yau Shiau | 2 | 0 | 0.34 |
| Ching-Chi Lin | 3 | 174 | 16.65 |
| D.T. Lee | 4 | 627 | 78.14 |