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

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

Review text

An input of the minimum hitting set of bundles problem is an set \(\mathcal E=\{e_1,e_2,\dots,e_n\}\) of \(n\) elements with non negative costs \(c_i\) for \(i=1,2,\dots,n\) and a collection \(\{S_1,S_2,\dots,S_m\}\) where \(S_i\) is a set of subsets of \(\mathcal E\). The aim is to find a solution with minimium total cost where a solution is a subset \(\mathcal E'\subseteq \mathcal E\) such that for every \(i=1,2,\dots,m\) there exists \(b\in S_i\) with \(b\subseteq \mathcal E'\) and the total cost is \(\sum \{c_i\mid e_i\in \mathcal E'\}\). There is given \(N(1-(1-\frac 1N)^M)\)-approximation polynomial time algorithm where \( N\) is the maximum number of subsets of \(\mathcal E\) per set and \(M\) is the maximum number of sets in which an element can appear. The scheme of algorithm is classical but the approximation ratio is the best one. Relation of this algorithm to similar problems is discussed.

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 importance of being biased
• The Minimum Satisfiability Problem

Cited in

(9)

• 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 Hitting Set of Bundles Problem
• scientific article; zbMATH DE number 2040676 (Why is no real title available?)
• On the minimum consistent subset problem
• Towards formal XAI: formally approximate minimal explanations of neural networks
• An efficient branch-and-bound solver for hitting set
• Attaining equilibria using control sets

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)