Computer Science and Engineering
menu MENU

CSE Seminar

Algorithms for Coping with Intractability and Uncertainty

Nikhil BansalProfessorEindhoven University of Technology
3725 Beyster Building


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 probabilitic approaches in designing these algorithms.


Nikhil Bansal is a researcher at CWI, Amsterdam and a professor at the Eindhoven University of Technology. He obtained his PhD from Carnegie Mellon University in 2003, and worked at the IBM T.J. Watson Research Center until 2011, where he also managed the Algorithms group.

He is broadly interested in theoretical computer science with focus on the design and analysis of algorithms, and has worked in related areas such as discrete mathematics, machine learning, combinatorial optimization and complexity. He has received several best paper awards for his work, including one at the FOCS 2011 conference. Currently, he is on the editorial boards of Journal of the ACM and Mathematics of Operations Research.


Cindy Estell

Faculty Host

Seth Pettie