Non-adaptive Stochastic Score Classification and Explainable Halfspace Evaluation

Rohan Ghuge, Anupam Gupta, Viswanath Nagarajan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings
EditorsKaren Aardal, Laura Sanità
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages14
ISBN (Print)9783031069000
StatePublished - 2022
Event23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 - Eindhoven, Netherlands
Duration: Jun 27 2022Jun 29 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13265 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022


  • Adaptivity
  • Approximation algorithms
  • Stochastic optimization
  • Stochastic probing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Non-adaptive Stochastic Score Classification and Explainable Halfspace Evaluation'. Together they form a unique fingerprint.

Cite this