On approximation of the vertex cover problem in hypergraphs

DOI10.1016/j.disopt.2004.11.002zbMath1168.90593OpenAlexW2060816316MaRDI QIDQ1779691

Michael S. Okun

Publication date: 1 June 2005

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2004.11.002

zbMATH Keywords

combinatorial optimizationapproximation algorithmsvertex coverset cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (8)

An approximation algorithm for submodular hitting set problem with linear penalties ⋮ From causes for database queries to repairs and model-based diagnosis and back ⋮ On the construction of a set of fundamental physical constants of unit and zero dimensions ⋮ Approximating vertex cover in dense hypergraphs ⋮ On the vertex cover number of 3-uniform hypergraph ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ A randomised approximation algorithm for the hitting set problem ⋮ Minimal covers of infinite hypergraphs

Cites Work

• Matchings and covers in hypergraphs
• On a theorem of Lovász on covers in \(r\)-partite hypergraphs
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Greedy Heuristic for the Set-Covering Problem
• Improved lower bounds on k‐independence
• Approximate Set Covering in Uniform Hypergraphs
• A Tight Analysis of the Greedy Algorithm for Set Cover

This page was built for publication: On approximation of the vertex cover problem in hypergraphs