Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation

Rohan Ghuge (), Anupam Gupta () and Viswanath Nagarajan ()
Additional contact information
Rohan Ghuge: Department of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Anupam Gupta: Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, New York, New York 10012
Viswanath Nagarajan: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109

Operations Research, 2025, vol. 73, issue 4, 2204-2222

Abstract: Sequential testing problems involve a complex system with several components, each of which is “working” with some independent probability. The outcome of each component can be determined by performing a test, which incurs some cost. The overall system status is given by a function f of the outcomes of its components. The goal is to evaluate this function f by performing tests at the minimum expected cost. Although there has been extensive prior work on this topic, provable approximation bounds are mainly limited to simple functions, like “ k -out-of- n ” and half-spaces. We consider significantly more general “score classification” functions, and we provide the first constant-factor approximation algorithm (improving over a previous logarithmic approximation ratio). Moreover, our policy is nonadaptive; it just involves performing tests in an a priori fixed order. We also consider the related half-space evaluation problem, where we want to evaluate some function on d half-spaces (e.g., the intersection of half-spaces). We show that our approach provides an O ( d 2 log d ) -approximation algorithm for this problem. Our algorithms also extend to the setting of “batched” tests, where multiple tests can be performed simultaneously while incurring an extra setup cost. Finally, we perform computational experiments that demonstrate the practical performance of our algorithm for score classification. We observe that, for most instances, the cost of our algorithm is within a factor of 1.5 of an information-theoretic lower bound on the optimal value.

Keywords: Optimization; stochastic optimization; sequential testing; adaptivity gaps; approximation algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0431 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:4:p:2204-2222

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().