Test score algorithms for budgeted stochastic utility maximization

Abstract
Motivated by recent developments in designing algorithms based on individual item scores for solving utility maximization problems, we study the framework of using test scores, defined as a statistic of observed individual item performance data, for solving the budgeted stochastic utility maximization problem. Algorithms based on individual item scores are practical when evaluating different combinations of items is difficult. We design a scoring measure to incorporate heterogeneous item costs as well as item values and show that a natural greedy algorithm that selects items solely based on their scores outputs solutions within a constant factor of the optimum for a broad class of utility functions. Our algorithms and approximation guarantees assume that test scores are noisy estimates of certain expected values with respect to marginal distributions of individual item values, thus making our algorithms practical and extending previous works that assume noiseless estimates. Moreover, we show how our algorithm can be adapted to the setting where items arrive in a streaming fashion while maintaining the same approximation guarantee. This is joint work with Milan Vojnovic and Se-Young Yun.

Short Bio
Dabeen Lee is currently a post-doc at the Discrete Mathematics Group at the Institute for Basic Science (IBS) in South Korea. He obtained his Ph.D. in Algorithms, Combinatorics, and Optimization (ACO) at Carnegie Mellon University. His research interests lie in operations research and optimization, and his latest research projects are about developing algorithms and mathematical programming frameworks for discrete optimization under uncertainty.