CMU-CS-12-120Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-12-120
Ravishankar Krishnaswamy May 2012 Ph.D. Thesis
Keywords:
Approximation Algorithms, Stochastic Optimization, Network Design, Scheduling
The focus of this thesis is on the design and analysis of algorithms for basic problems in Stochastic Optimization, specifically a class of fundamental combinatorial optimization problems where there is some form of uncertainty in the input. Since many interesting optimization problems are computationally intractable (NP-Hard), we resort to designing approximation algorithms which provably output good solutions. However, a common assumption in traditional algorithms is that the exact input is known in advance. What if this is not the case? What if there is uncertainty in the input?
With the growing size of input data and their typically distributed nature
(e.g., cloud computing), it has become imperative for algorithms to handle
varying forms of input uncertainty. Current techniques, however, are not
robust enough to deal with many of these problems, thus necessitating the
need for new algorithmic tools. Answering such questions, and more generally
identifying the tools for solving such problems, is the focus of this thesis.
The exact problems we study in this thesis are the following: (a) the
135 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |