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.
Users
Please
log in to take part in the discussion (add own reviews or comments).