An Efficient Branch-and-Bound Solver for Hitting Set

10/22/2021
by   Thomas Bläsius, et al.
0

The hitting set problem asks for a collection of sets over a universe U to find a minimum subset of U that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instances from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset