Combinatorial optimization captures many natural decision-making problems such as matching, load balancing, assortment optimization, network design, and submodular optimization. In this talk, I will focus on combinatorial problems under uncertainty; specifically when we only have partial knowledge about the input. Solutions to such problems are sequential decision processes that make decisions one by one “adaptively” (depending on prior observations). While such adaptive solutions achieve the best objective, the inherently sequential nature makes them undesirable in many applications. My current research seeks to answer the following: how well can solutions with only a few adaptive rounds approximate fully-adaptive solutions? In this talk, I will formally define the model, and discuss techniques used to answer this question for the stochastic submodular cover problem, which captures problems in domains like sensor placement, medical diagnosis, active learning, and hypothesis testing. I will also state limited adaptivity results that I have obtained for the stochastic score classification and dueling bandits problems. I will conclude the talk with some future work and open problems.

Presenter Bio:
Rohan Ghuge is a Ph.D. candidate in the department of Industrial and Operations Engineering (IOE) at the University of Michigan where he is advised by Dr. Viswanath Nagarajan. His research interests are in optimization under uncertainty, specifically in stochastic combinatorial optimization. His dissertation research explores the role of adaptivity in stochastic combinatorial optimization. He has also worked on designing algorithms for problems arising in domains like assortment optimization, network design and online learning.