CMU-CS-18-111 Computer Science Department School of Computer Science, Carnegie Mellon University
Combinatorial Optimization Under Uncertainty: Sahil Singla Ph.D. Thesis August 2018
Combinatorial optimization captures many natural problems such as matching, load balancing, social welfare, 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 and 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 the input is revealed to us element-by-element and we have to make irrevocable decisions. Depending on whether we can control the revelation order of these elements, we separate our models and algorithms into two groups.
(B) Stopping-Time Algorithms: In these models the input is revealed elementby-element in an order that we cannot control. These models are inspired from work in the field of Optimal Stopping Theory. In particular, we consider combinatorial problems when either we have stochastic knowledge about the input but the revelation order is chosen by an adversary (the Prophet Inequality model) or when we have no prior knowledge about the input but the revelation order is chosen uniformly at random (the Secretary model).
Manuel Blum (Co-Chair) Anupam Gupta (Co-Chair) Robert D. Kleinberg (Cornell University) R. Ravi (Tepper/CSD) Jan Vondrák (Stanford University)
Srinvasan Seshan, Head, Computer Science Department
| |
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |