AF: Small: Adaptivity and Learning in Stochastic Combinatorial Optimization

Data uncertainty is ubiquitous in several algorithmic applications such as healthcare, retail, transportation and robotics. For example, medical diagnosis involves performing tests without precise knowledge of the underlying condition, capacity planning in the retail industry involves coming up with inventory levels without full knowledge of future demand, and path planning in robotics involves finding routes with limited information about the ambient space. In these and many other applications, one needs to design algorithms using only partial input information (typically obtained from historical data). This project aims to design algorithms with theoretical performance guarantees for some fundamental problems arising in these applications. Results from this project will contribute to and establish new connections between theoretical computer science, operations research, and machine learning. The project also involves mentoring graduate and undergraduate students, developing new course material, and organizing workshops to broaden participation in graduate programs. This project models uncertainty using stochastic optimization, where unknown input parameters are treated as random variables. Algorithms for such problems are often very sequential, where each step makes some decision and observes a corresponding random variable. The first goal in this project is to obtain parallelizable algorithms for stochastic optimization, which corresponds to making decisions in a small number of sequential rounds. This research direction involves quantifying the tradeoff between approximation quality (relative to the optimal sequential solution) and the number of sequential rounds. The second goal in this project is to obtain algorithms for stochastic optimization when the probability distribution of the input is unknown. This research direction is motivated by applications where historical data is inaccurate or unavailable. This direction will utilize and combine techniques from approximation algorithms and online learning. The project will address both these research directions in the context of fundamental combinatorial optimization problems such as knapsack, set cover, and influence maximization. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.