Algorithms for implicit hitting set problems

MaRDI QIDQ5365067zbMATH OpenFDO

Authors Karthekeyan Chandrasekaran, Erick Moreno-Centeno, Richard Karp, Santosh S. Vempala

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133084

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• A randomised approximation algorithm for the hitting set problem
• A randomised approximation algorithm for the hitting set problem
• An efficient fixed-parameter algorithm for 3-hitting set
• Hitting sets when the VC-dimension is small
• scientific article; zbMATH DE number 3876618

Cited in

(15)

• An improved algorithm for the red-blue hitting set problem with the consecutive ones property
• Sequential model-based diagnosis by systematic search
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Sharp concentration of hitting size for random set systems
• An implicit cover problem in wild population study
• Approximation algorithms in the successive hitting set model
• A variant of Reiter's hitting-set algorithm
• Approximating activation edge-cover and facility location problems
• Anytime approximate formal feature attribution
• Towards universally accessible SAT technology
• PACE solver description: UzL exact solver for one-sided crossing minimization
• Unsupervised learning with GNNs for QUBO-based combinatorial optimization
• scientific article; zbMATH DE number 7561664 (Why is no real title available?)
• Computing in combinatorial optimization
• An efficient branch-and-bound solver for hitting set

This page was built for publication: Algorithms for implicit hitting set problems

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