Algorithms for the Unit-Cost Stochastic Score Classification Problem

Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik, Naifeng Liu

    Research output: Contribution to journalArticlepeer-review


    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 pi 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 languageEnglish (US)
    Pages (from-to)3054-3074
    Number of pages21
    Issue number10
    StatePublished - Oct 2022


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

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics


    Dive into the research topics of 'Algorithms for the Unit-Cost Stochastic Score Classification Problem'. Together they form a unique fingerprint.

    Cite this