Algorithms for coping with intractability and uncertainty

Over the years, several ingenious and powerful algorithms have been developed for various fundamental problems such as shortest paths, minimum cost spanning trees, perfect matchings and so on. But real world problems are rarely so clean, and usually involve multiple side-constraints and objectives on top of the basic underlying problem, making it NP-Hard or intractable. Another issue is the presence of uncertainty that can make the computation of an exact answer impossible. This uncertainty could be due to imprecise or incomplete input data, or could even be inherent, e.g. a scheduler may have to decide which job to run next without the knowledge of future job arrivals.I will describe several recent algorithmic approaches to cope with these issues of intractability and uncertainty. A key underlying theme will be the use of high-dimensional geometric and probabilistic approaches in designing these algorithms.