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

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

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)

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

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)