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 email address is being protected from spambots. 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.
Don't have an account?
Overview
The document is a Technical Support Package from NASA, specifically referencing NPO-30584, which discusses two methods for efficiently solving the Hitting-Set Problem. This problem is significant in various fields, including computer science, operations research, and combinatorial optimization, as it involves selecting a minimal subset of elements that intersects with all sets in a given collection.
The document emphasizes the importance of making aerospace-related developments accessible for broader technological, scientific, and commercial applications. It is part of NASA's Commercial Technology Program, which aims to promote the dissemination of research findings and technological advancements. The information provided is intended to support researchers, engineers, and industry professionals interested in applying these methods to real-world problems.
The Hitting-Set Problem is a classic problem in combinatorial optimization, where the goal is to find the smallest set of elements that hits all subsets in a collection. The document likely outlines the two proposed methods, detailing their algorithms, efficiency, and potential applications. While the specific details of these methods are not included in the provided text, they are expected to offer innovative approaches that improve upon existing solutions.
Additionally, the document includes contact information for further assistance, directing readers to the NASA Scientific and Technical Information (STI) Program Office. This office provides access to a wide range of publications and resources related to NASA's research and technology initiatives. The STI Help Desk is available for inquiries, offering support through various communication channels.
The document also includes a disclaimer stating that the United States Government and its representatives do not assume liability for the use of the information contained within. It clarifies that any mention of trade names or manufacturers is for identification purposes only and does not imply official endorsement by NASA.
In summary, this Technical Support Package serves as a resource for understanding and applying two efficient methods for the Hitting-Set Problem, while also promoting the broader dissemination of NASA's technological advancements and research findings. It highlights NASA's commitment to supporting innovation and collaboration in various fields.
