On the Minimum Hitting Set of Bundles Problem

DOI10.1007/978-3-540-68880-8_3zbMATH Open1143.90372OpenAlexW1843037014MaRDI QIDQ3511409FDOQ3511409

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

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

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)

Cites Work

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

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)