TY - GEN

T1 - Non-adaptive Stochastic Score Classification and Explainable Halfspace Evaluation

AU - Ghuge, Rohan

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

N1 - Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

PY - 2022

Y1 - 2022

N2 - We consider the stochastic score classification problem. There are several binary tests, where each test i is associated with a probability pi of being positive, a cost ci, and a weight ai. The score of an outcome is a weighted sum of all positive tests, and the range of possible scores is partitioned into intervals corresponding to different classes. The goal is to perform tests sequentially (and possibly adaptively) so as to identify the class at the minimum expected cost. We provide the first constant-factor approximation algorithm for this problem, which improves over the previously-known logarithmic approximation ratio. Moreover, our algorithm is non adaptive: it just involves performing tests in a fixed order until the class is identified. Our approach also extends to the d-dimensional score classification problem and the “explainable” stochastic halfspace evaluation problem (where we want to evaluate some function on d halfspaces). We obtain an O(d2log d) -approximation algorithm for both these extensions. 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 50 % of an information-theoretic lower bound on the optimal value.

AB - We consider the stochastic score classification problem. There are several binary tests, where each test i is associated with a probability pi of being positive, a cost ci, and a weight ai. The score of an outcome is a weighted sum of all positive tests, and the range of possible scores is partitioned into intervals corresponding to different classes. The goal is to perform tests sequentially (and possibly adaptively) so as to identify the class at the minimum expected cost. We provide the first constant-factor approximation algorithm for this problem, which improves over the previously-known logarithmic approximation ratio. Moreover, our algorithm is non adaptive: it just involves performing tests in a fixed order until the class is identified. Our approach also extends to the d-dimensional score classification problem and the “explainable” stochastic halfspace evaluation problem (where we want to evaluate some function on d halfspaces). We obtain an O(d2log d) -approximation algorithm for both these extensions. 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 50 % of an information-theoretic lower bound on the optimal value.

KW - Adaptivity

KW - Approximation algorithms

KW - Stochastic optimization

KW - Stochastic probing

UR - http://www.scopus.com/inward/record.url?scp=85131917042&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85131917042&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-06901-7_21

DO - 10.1007/978-3-031-06901-7_21

M3 - Conference contribution

AN - SCOPUS:85131917042

SN - 9783031069000

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 277

EP - 290

BT - Integer Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings

A2 - Aardal, Karen

A2 - Sanità, Laura

PB - Springer Science and Business Media Deutschland GmbH

T2 - 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022

Y2 - 27 June 2022 through 29 June 2022

ER -