An approximation algorithm for the partial vertex cover problem in hypergraphs

DOI10.1007/S10878-014-9793-2zbMATH Open1360.90219OpenAlexW2054248368MaRDI QIDQ5963655FDOQ5963655

Anand Srivastav, Mourad El Ouali, Helena Fohlin

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

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmshypergraphsvertex coverprobabilistic methods

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• Randomized approximation for the set multicover problem in hypergraphs
• On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
• Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
• On approximation of the vertex cover problem in hypergraphs
• Approximation algorithm for the multicovering problem
• Local approximations for maximum partial subgraph problem.
• Local ratio method on partial set multi-cover
• 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
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Approximation of Partial Capacitated Vertex Cover
• Approximation of set multi-cover via hypergraph matching

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)