On the minimum hitting set of bundles problem

DOI10.1016/J.TCS.2009.08.017MaRDI QIDQ1035686zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On the Minimum Hitting Set of Bundles Problem
• Parameterizations of hitting set of bundles and inverse scope
• An efficient fixed-parameter algorithm for 3-hitting set
• Near-linear approximation algorithms for geometric hitting sets
• Near-linear approximation algorithms for geometric hitting sets

Cites work

• A new multilayered {PCP} and the hardness of hypergraph vertex cover
• Approximating MIN 2-SAT and MIN 3-SAT
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Dynamic programming solution for multiple query optimization problem
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• On approximation algorithms for the minimum satisfiability problem
• On dependent randomized rounding algorithms
• Structure preserving reductions among convex optimization problems
• The Minimum Satisfiability Problem
• The importance of being biased

Cited in

(8)

• scientific article; zbMATH DE number 2040676 (Why is no real title available?)
• Towards formal XAI: formally approximate minimal explanations of neural networks
• On the Minimum Hitting Set of Bundles Problem
• Minimal approximate hitting sets and rule templates
• Minimum hitting set of interval bundles problem: computational complexity and approximability
• Parameterizations of hitting set of bundles and inverse scope
• On the minimum consistent subset problem
• An efficient branch-and-bound solver for hitting set

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

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