English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper, we consider the minimum unweighted Vertex Cover problem with Hard Capacity constraints (VCHC) on multigraphs and hypergraphs. Given a graph, the objective of VCHC is to find a smallest multiset of vertices that cover all edges, under the constraints that each vertex can only cover a limited number of incident edges, and the number of available copies of each vertex is bounded. This problem generalizes the classical unweighted vertex cover problem. Here we restrict our attention to unweighted instances, since the weighted version of VCHC is as hard as the set cover problem, as shown by Chuzhoy and Naor (FOCS 2002).We obtain improved approximation algorithms for VCHC on multigraphs and hypergraphs. This problem has first been studied by Saha and Khuller (ICALP 2012). They proposed a 38-approximation for multigraphs, and a max {6 f, 65}-approximation for hypergraphs, where f is the size of the largest hyperedge. In this paper, we significantly improve these approximation ratios to 1 + 2/√3 < 2.155 and 2 f respectively. In the case of multigraphs, our approximation ratio is very close to the longstanding bound of 2 for the classical vertex cover problem. Our algorithms consist of a two-step process, each based on rounding an appropriate linear program. In particular, for multigraphs, the analysis in the second step relies on identifying a matching structure within any extreme point solution.Furthermore, we consider the partial VCHC problem in which one only needs to cover all but ℓ edges. We propose a generic reduction from partial VCHC on f-hypergraphs to VCHC on (f + 1)-hypergraphs, with a small loss in the approximation factor. In particular, we present a (2f + 2)(1 + ∊)-approximation algorithm for partial VCHC on f-hypergraphs.Singapore. Agency for Science, Technology and ResearchNational Science Foundation (U.S.) (Contract CCF-1115849)United States. Office of Naval Research (Grant N00014-05-1-0148

Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs