Computer Science Thesis Proposal

Friday, November 10, 2017 - 12:00pm


3002 Newell-Simon Hall



Combinatorial Optimization Under Uncertainty: Probing and Stopping-Time Algorithms

Combinatorial optimization  captures many natural problems such as matching, load balancing, social welfare, orienteering, network design, clustering, and submodular optimization. Classically, these problems have been studied in the full-information setting, i.e., where the entire input---an objective function with some constraints---is given and the goal is to select a feasible set to maximize/minimize the objective function. In this thesis we focus on combinatorial  problems in an uncertain environment where we only have partial knowledge about the input. In particular, we study  models where  uncertainty in the input is revealed to us element-by-element, and we have to make immediate and irrevocable decisions. Depending on whether we can control the revelation order of these elements, we separate our  models and algorithms into two classes.

(a) Probing Algorithms: In these models we have some stochastic knowledge about the input, 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 of them as either probing incurs a price (the price of information model) or there are probing constraints (the constrained stochastic probing model). Some examples are the Pandora's box and the best-box problems.

(b) Stopping-Time Algorithms: In these models the uncertainty in the input is revealed element-by-element in an order  that we cannot control. These models are inspired from work in the field of Stopping Theory. In particular, we consider combinatorial problems when the revelation order is either chosen by an adversary (the Prophet Inequality model) or chosen uniformly at random (the Secretary model).

Thesis Committee:
Manuel Blum (Co-chair)
Anupam Gupta (Co-chair)
R. Ravi
Robert D. Kleinberg (Cornell University)
Jan Vondrak (Stanford University)

Copy of Thesis Summary

For More Information, Contact:


Thesis Proposal