Performance Bounds for Binary Testing with Arbitrary Weights.
Abstract
Binary testing concerns finding good algorithms to solve the class of binary identification problems. A binary identification problem has as input a set of objects, including one marked as distinguished (e.g., faulty), for each object an a priori estimate that it is the distinguished object, and a set of tests. Output is a testing procedure to isolate the distinguished object. One seeks minimal cost testing procedures where cost is the average cost of isolation, summed over all objects. This is a problem schema for the diagnosis problem: applications occur in medicine, systematic biology, machine fault location, quality control and elsewhere. In this paper we extend work of Garey and Graham to assess the capability of fast approximation rule, the binary splitting rule, to give near optimal testing procedures when the a priori estimates are arbitrary. We find conditions on the test set such that approximation error reduces nearly to, that of the equally likely a priori estimate case of Garey and Graham and find another upper bound on approximation error for the same test set condition which works very well under a priori estimate assumptions where the first results is poor. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1982
- Accession Number
- ADA117493
Entities
People
- Donald W. Loveland
Organizations
- Duke University