Improved Approximation of Maximum Vertex Coverage Problem on Bipartite Graphs

DOI10.1137/130931059zbMath1310.90095OpenAlexW2040480264MaRDI QIDQ2935262

Nicola Apollonio, Bruno Simeone

Publication date: 22 December 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/130931059

zbMATH Keywords

LP roundingtransversal numbervertex coverage

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Indiscernibility structures induced from function sets : Graph and digraph case ⋮ Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs ⋮ Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ Simplicial complexes and closure systems induced by indistinguishability relations ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Maximum Weighted Independent Sets with a Budget ⋮ Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs