Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation

• 成果类型: Article
• 署名作者: Ghuge, Rohan; Gupta, Anupam; Nagarajan, Viswanath
• 署名单位: University System of Georgia; Georgia Institute of Technology; New York University; University of Michigan System; University of Michigan
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0431
• 发表日期: 2025
• 页码: 2204-2222
• 关键词: approximation algorithms

摘要

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 k-out-of-n 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.