## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 3054-3074 |

Number of pages | 21 |

Journal | Algorithmica |

Volume | 84 |

Issue number | 10 |

DOIs | |

State | Published - Oct 2022 |

## Keywords

- Adaptivity
- Approximation algorithms
- Sequential testing
- Stochastic probing
- Symmetric boolean functions

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics