An Exact Fast Algorithm for Minimum Hitting Set
Lei Shi, Xuan Cai · 2010
We propose a branch-and-reduce algorithm to solve the Minimum Hitting Set Problem in this paper and use a recently developed technique called measure and conquer to perform analysis on the algorithm. By applying such technique and quasiconvex programming when optimizing the analysis results, we prove that our algorithm can solve the Minimum Hitting Set Problem in O(1.23801n) and polynomial space.