CS700:Graduate Seminar in Computer Science & Informatics

Solving discrete optimization problems: mathematical programming to the rescue

A discrete optimization problem is one in which we seek to find an optimum solution, usually under a linear objective function, among a finite set of feasible solutions. For example, in the traveling salesman problem, the feasible solutions are tours in an edge- weighted graph, and we seek to find the shortest tour. Such problems arise in a variety of contexts, including some particularly important ones: http://xkcd.com/287/ . The structure of the feasible solution space is critical in designing algorithms for discrete optimization problems, and one approach that's proven itself particularly fruitful has been to map the feasible solution space to a (related) vector space and to optimize over the corresponding geometric object in the vector space. We usually end up somewhere in the intersection of algorithms, graph theory, and linear algebra. I will give an overview of this method and highlight some of its successes, including a recent application which saved lives1!

1 David Abraham, Avrim Blum, and Tuomas Sandholm, Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges, ACM-EC 2007.
Ojas Parekh is Assistant Professor of Mathematics and Computer Science at Emory University. His research interest is in the application of mathematical programming techniques to the theory of computation, focusing in particular on applications to combinatorial optimization and approximation algorithms for hard problems.