Performance bounds for binary testing with arbitrary weights (Q1083851)

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 regarded 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 \textit{M. R. Garey} and \textit{R. L. Graham} [ibid. 3, 347-355 (1974; Zbl 0276.68023)] to assess the capability of a 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 such that the 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 conditions which works very well under a priori estimate assumptions where the first result is poor.