On the minimum hitting set of bundles problem

DOI10.1016/j.tcs.2009.08.017zbMath1175.68557OpenAlexW2786382671MaRDI QIDQ1035686

Eric Angel, Evripidis Bampis, Laurent Gourvès

Publication date: 4 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2149

zbMATH Keywords

approximation algorithmmin \(k\)-satminimum hitting set

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (2)

Minimum hitting set of interval bundles problem: computational complexity and approximability ⋮ Parameterizations of hitting set of bundles and inverse scope

Cites Work

• Dynamic programming solution for multiple query optimization problem
• Structure preserving reductions among convex optimization problems
• On dependent randomized rounding algorithms
• On approximation algorithms for the minimum satisfiability problem
• Approximating MIN 2-SAT and MIN 3-SAT
• 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
• The importance of being biased
• A new multilayered PCP and the hardness of hypergraph vertex cover
• The Minimum Satisfiability Problem

This page was built for publication: On the minimum hitting set of bundles problem