On the Minimum Hitting Set of Bundles Problem

DOI10.1007/978-3-540-68880-8_3MaRDI QIDQ3511409zbMATH OpenOpenAlexFDO

Authors Laurent Gourvès, Eric Angel, Evripidis Bampis

Publication date 10 July 2008

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmminimum hitting setMin \(k\)-Sat

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) 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
• On approximation algorithms for the minimum satisfiability problem
• The budgeted maximum coverage problem

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

(5)

• Minimum hitting set of interval bundles problem: computational complexity and approximability
• Parameterizations of hitting set of bundles and inverse scope
• On the minimum hitting set of bundles problem
• 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 Q3511409)