Algorithms & Randomness Center (ARC)
Viswanath Nagarajan (University of Michigan)
April 3, 2023
Klaus 1116 - 11:00 am
Title: Stochastic Score Classification and Halfspace Intersection
Abstract: In sequential testing, we have a complex system with several components, each of which is "working" or "failed" with some independent probability. We are interested in evaluating the system status, which is a function of the statuses of its components. The goal is to design a policy that minimizes the expected cost of testing. Prior work has mainly focused on simple functions like k-of-n and halfspaces. We consider more general "score classification" functions, and provide the first constant-factor approximation algorithm. Our result improves over a previous logarithmic approximation ratio. Moreover, our policy is non adaptive: it just involves performing tests in an a-priori fixed order. Finally, in computational experiments on random instances, we observe that the cost of our algorithm is typically within 50% of an information-theoretic lower bound.
---
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
