Speaker

Viswanath Nagarajan, Associate Professor, Industrial and Operations Engineering, University of Michigan

Abstract

We study the stochastic submodular cover problem, where one needs to select a subset of stochastic items to cover a submodular function at a minimum expected cost. Solutions in this setting correspond to sequential decision processes that select items one by one adaptively, depending on prior observations. While such adaptive solutions achieve the best objective, they are inherently sequential, which is undesirable in many applications. We show how to obtain solutions that approximate fully adaptive solutions using only a few “rounds” of adaptivity. We study both independent and correlated settings, proving smooth tradeoffs between the number of adaptive rounds and the solution quality. We also present experimental results demonstrating that a few rounds of adaptivity suffice to obtain high-quality solutions in practice.

Bio

Viswanath is an associate professor of Industrial and Operations Engineering at the University of Michigan. From 2009-2014, he was a research staff member in the Business Analytics and Mathematical Sciences division at IBM T.J. Watson Research Center. Viswanath received his Ph.D. from Carnegie Mellon University (2009) and his bachelor’s degree from the Indian Institute of Technology, Bombay (2003). His current research is in combinatorial optimization, approximation algorithms, and stochastic optimization. Viswanath’s awards include an NSF CAREER award (2018), the best paper award at the European Symposium on Algorithms (ESA 2010), and two outstanding technical achievement awards at IBM (2012 and 2014).