Accession Number : ADA117493

Title :   Performance Bounds for Binary Testing with Arbitrary Weights.

Descriptive Note : Technical rept.,

Corporate Author : DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE

Personal Author(s) : Loveland,Donald W

PDF Url : ADA117493

Report Date : Mar 1982

Pagination or Media Count : 43

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)

Descriptors :   *Binary arithmetic, *Weighting functions, *Algorithms, *Problem solving, Identification, Diagnosis(General), Weight, Input, Output, Approximation(Mathematics), Errors, Limitations

Subject Categories : Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE