An approximation algorithm for the partial vertex cover problem in hypergraphs

DOI10.1007/S10878-014-9793-2MaRDI QIDQ5963655zbMATHOpenAlexFDO

Authors Mourad El Ouali, Helena Fohlin, Anand Srivastav

Publication date 23 February 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-014-9793-2

zbMATH Keywords

combinatorial optimizationapproximation algorithmshypergraphsvertex coverprobabilistic methods

Mathematics Subject Classification ID

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

Recommendations

• A randomised approximation algorithm for the partial vertex cover problem in hypergraphs
• On approximation of the vertex cover problem in hypergraphs
• Partial covering of hypergraphs
• Approximating vertex cover in dense hypergraphs
• Publication:4952635

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 1947055 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1445320 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A new polynomial-time algorithm for linear programming
• A threshold of ln n for approximating set cover
• Algorithmic construction of sets for k -restrictions
• Approximate Set Covering in Uniform Hypergraphs
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation algorithms for partial covering problems
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Improved approximation algorithms for maximum graph partitioning problems
• New constructions of weak \(\varepsilon\)-nets
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• Randomized approximation of bounded multicovering problems
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(17)

• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Approximation algorithm for the multicovering problem
• Local ratio method on partial set multi-cover
• Approximation of Partial Capacitated Vertex Cover
• Approximation of set multi-cover via hypergraph matching
• A randomised approximation algorithm for the hitting set problem
• Local approximations for maximum partial subgraph problem.
• Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
• On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
• Multi-start iterated tabu search for the minimum weight vertex cover problem
• A randomised approximation algorithm for the partial vertex cover problem in hypergraphs
• Solving vertex cover in polynomial time on hyperbolic random graphs
• A randomised approximation algorithm for the hitting set problem
• On approximation of the vertex cover problem in hypergraphs
• Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs
• Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
• Randomized approximation for the set multicover problem in hypergraphs

This page was built for publication: An approximation algorithm for the partial vertex cover problem in hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963655)