An Efficient Algorithm for Finding Certain Minimum-Cost Procedures for Making Binary Decisions

James Robert Slagle · Journal of the ACM · 1964

This paper is concerned with a class of procedures for making true-false decisions which depend on the outcome of eo sequence of elementary, binary tests.Certain of these procedures, calJed s-procedures, are conveniently represented by Boolean expressions (whose variables represent the elementary, bil~ary tests) and are easily carried out.If we are given the cost of applying each elementary, bina.rytest and the (a priori) prob'~bility of its outcome, the (average) cost of a procedure may be computed.Th.e genera!problem treated is to find efficiently a minimum-cost procedure equiv,~dent to a given s-procedure with known costs and probabilities for its elementt~ry, binary tests.Among the facts proved are two theorems showing that, under certain1 coi~ditions, the s-procedure found by a specified, efficient algorithm has mhfimum cost.The theorems and the etticient algorithm are used to solve illustrative problems in ti, e areas of computer programming, solving mat}mmatical problems, personnel selection, and medical diagnosis.

Cited by 29 works. doi:10.1145/321229.321230 Open-access PDF

Authors