| Two Methods for Efficient Solution of the Hitting-Set Problem |
|
|
| Mar 01 2005 | |
|
advertisement: A paper addresses much of the same subject matter as that of “Fast Algorithms for Model-Based Diagnosis” (NPO-30582), which appears elsewhere in this issue of NASA Tech Briefs.
However, in the paper, the emphasis is more on the hitting-set problem (also known as the transversal problem), which is well known among experts in combinatorics. The authors’ primary interest in the hitting-set problem lies in its connection to the diagnosis problem: it is a theorem of model-based diagnosis that in the set-theory representation of the components of a system, the minimal diagnoses of a system are the minimal hitting sets of the system. In the paper, the hitting-set problem (and, hence, the diagnosis problem) is translated from a combinatorial to a computational problem by mapping it onto the Boolean satisfiability and integer-programming problems. The paper goes on to describe developments nearly identical to those summarized in the cited companion NASA Tech Briefs article, including the utilization of Boolean-satisfiability and integer-programming techniques to reduce the computation time and/or memory needed to solve the hitting-set problem.This work was done by Farrokh Vatan and Amir Fijany of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category. In accordance with Public Law 96-517, the contractor has elected to retain title to this invention. Inquiries concerning rights for its commercial use should be addressed to: Innovative Technology Assets Management JPL Mail Stop 202-233 4800 Oak Grove Drive Pasadena, CA 91109-8099 (818) 354-2240 E-mail: This e-mail address is being protected from spam bots, you need JavaScript enabled to view it Refer to NPO-30584, volume and number of this NASA Tech Briefs issue, and the page number. This Brief includes a Technical Support Package (TSP).
Two Methods for Efficient Solution of the Hitting-Set Problem (reference NPO-30584) is currently available for download from the TSP library. Login first to download.
|
