Algorithms for the Unit-Cost Stochastic Score Classification Problem

Consider the following Stochastic Score Classification problem. A doctor is assessing a patient’s risk of developing a disease and can perform n different binary tests on the patient. The probability that test i is positive is p_i and the outcomes of the n tests are independent. A patient’s score is the total number of positive tests. Possible scores thus range between 0 and n. This range is divided into subranges, corresponding to risk classes (e.g., LOW, MEDIUM, or HIGH risk). Each test has an associated cost. To reduce testing cost, instead of performing all tests and determining an exact score, the doctor can perform tests sequentially and stop testing when it is possible to determine the patient’s risk class. The problem is to determine the order in which the doctor should perform the tests, so as to minimize expected testing cost. We address the unit-cost case of the Stochastic Score Classification problem, and provide polynomial-time approximation algorithms for adaptive and non-adaptive versions of the problem. We also pose a number of open questions.