Sahil Singla, Princeton University

Abstract

Combinatorial optimization is important because it captures many natural problems, e.g., spanning tree, bipartite matching, set cover, network design, clustering, and submodular/subadditive optimization. Classically, these problems have been studied in the full-information setting where the entire input---an objective function and some  constraints---is given and the goal is to select a feasible set to maximize/minimize the objective. In this talk we focus on combinatorial problems when the input is uncertain. In particular, we have some stochastic knowledge about the input (a probability distribution), but the uncertainty of an element realizes only after we probe it. We can choose the order and the set of elements to probe; however, we do not wish to probe all the elements as either probing incurs a price (the price of information) or there are probing constraints (the constrained stochastic probing). We design optimal/approximation algorithms for such problems and study the benefits of adaptivity.