An approximation algorithm for the partial vertex cover problem in hypergraphs

DOI10.1007/S10878-014-9793-2MaRDI QIDQ5963655zbMATH OpenOpenAlexFDO

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

approximation algorithmscombinatorial optimizationhypergraphsprobabilistic methodsvertex cover

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 1445320

Cites work

• 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 maximization problems arising in graph partitioning
• Approximation algorithms for partial covering problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• 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?)
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum graph partitioning problems
• New constructions of weak -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)

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

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)