ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

17. Control Theory and Optimization

1991 MS Classification: 90, 05, 68 Goemans, Michel, Université catholique de Louvain, Belgium, and Massachusetts Institute of Technology, USA Semidefinite programming and combinatorial optimization

Convex optimization, and more specifically semidefinite programming, has found many applications in combinatorial optimization. The LP bound in coding, the theta function for the stability number, or spectral bounds on graph partitioning and sparsest cut can all be interpreted in terms of semidefinite programs, among many other results. Recently, other applications have been found ranging from the automatic generation of valid inequalities for integer programs, to randomized approximation algorithms for the maximum cut and other combinatorial problems such as the bandwidth problem. In this talk, I will survey some of these developments and applications, and their limitations.

ICM 1998 Berlin · Plenary and Invited Lectures