Two Methods for Efficient Solution of the Hitting-Set Problem
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
This week's Question: The Drone Racing League announced on Wednesday that it had signed deals to broadcast a 10-episode season on ESPN and ESPN2, along with the European stations Sky Sports Mix and 7Sports. According to league officials, stationary pilots...
Subscribe today to receive the INSIDER, a FREE e-mail newsletter from NASA Tech Briefs featuring exclusive previews of upcoming articles, late breaking NASA and industry news, hot products and design ideas, links to online resources, and much more.