MIT Department of Electrical Engineering & Computer Science

DATE: MONDAY, OCTOBER 24, 1994

TIME: TALK AT 2:45
Refreshments at 3:00

PLACE NE43-518

Approximation Algorithms and Linear Programming
Eva Tardos
Cornell University

Abstract

The most well-known theorem in combinatorial optimization is the classical max-flow min-cut theorem of Ford and Fulkerson. This theorem can be viewed as special case of the linear programming duality theorem, and it also serves as the basis for finding efficient algorithms to solve these two problems. Efficient algorithms for many other combinatorial optimization problems are based on min-max theorems that are special cases of the linear programming duality theorem in a similar way.

However, many important combinatorial optimization problems seem too hard to solve optimally; for example, this is the case for NP-hard problems. It is natural to look, instead, for efficient approximation algorithms for these problems. In recent years, fast approximation algorithms have also been developed for many polynomially solvable problems, where all known algorithms that find optimal solutions have large, albeit polynomial, complexity.

Linear programming techniques have also proved to be useful in designing approximation algorithms. One way to use linear programming is to set up a linear program whose integer solutions correspond to solutions of the combinatorial optimization problem, find an optimal fractional solution, and round it. While this approach has been widely used in practice, it is more recent that approximation algorithms with a provable worst case performance have been designed along these lines.

The immediate next question is how efficiently one can solve the linear program related to a particular combinatorial optimization problem. While linear programming is solvable in polynomial time, the worst case complexity of general linear programming is quite high, and in many combinatorial applications the related linear program is quite large. In some cases approximate solutions can be found much more efficiently using more direct combinatorial methods.

In this talk we will survey some of these results and proof techniques.

HOST: John Guttag