%0 Conference Paper %1 paper:abreu:2009 %A Abreu, Rui %A van Gemund, Arjan J.C. %B Proceedings of the 20th International Workshop on Principles of Diagnosis %D 2009 %K MCS diagnosis dx09 hitting-set minimal %P 51--58 %T A Statistics-directed Minimal Hitting Set Algorithm %X Generating minimal hitting sets of a collection of sets is known to be NPhard, necessitating heuristic approaches to handle large problems. In this paper a low-cost, approximate minimal hitting set (MHS) algorithm, coined Staccato, is presented. Staccato uses a heuristic function, borrowed from a lightweight, statistics-based software fault localization approach, to guide the MHS search. Given the nature of the heuristic function, Staccato is specially tailored to model-based diagnosis problems (where each MHS solution is a diagnosis to the problem), although well-suited for other application domains as well. We apply Staccato in the context of model-based diagnosis and show that even for small problems our approach is orders of magnitude faster than the brute-force approach, while still capturing all important solutions. Furthermore, due to its low cost complexity, we also show that Staccato is amenable to large problems including millions of variables.

@inproceedings{paper:abreu:2009, abstract = {Generating minimal hitting sets of a collection of sets is known to be NPhard, necessitating heuristic approaches to handle large problems. In this paper a low-cost, approximate minimal hitting set (MHS) algorithm, coined Staccato, is presented. Staccato uses a heuristic function, borrowed from a lightweight, statistics-based software fault localization approach, to guide the MHS search. Given the nature of the heuristic function, Staccato is specially tailored to model-based diagnosis problems (where each MHS solution is a diagnosis to the problem), although well-suited for other application domains as well. We apply Staccato in the context of model-based diagnosis and show that even for small problems our approach is orders of magnitude faster than the brute-force approach, while still capturing all important solutions. Furthermore, due to its low cost complexity, we also show that Staccato is amenable to large problems including millions of variables.}, added-at = {2009-06-18T15:48:21.000+0200}, author = {Abreu, Rui and van Gemund, Arjan J.C.}, biburl = {https://www.bibsonomy.org/bibtex/26dda2dcf83d19d2ed0562d5a907ccd05/mschuber}, booktitle = {Proceedings of the 20th International Workshop on Principles of Diagnosis}, interhash = {34a0877435365cf06e08c22c8261be36}, intrahash = {6dda2dcf83d19d2ed0562d5a907ccd05}, keywords = {MCS diagnosis dx09 hitting-set minimal}, pages = {51--58}, timestamp = {2009-06-18T15:48:21.000+0200}, title = {A Statistics-directed Minimal Hitting Set Algorithm}, year = 2009 }