EURO Summer Institute 2010
Klagenfurt, Austria, August 20 - September 4, 2010
Uni Logo
Department of Mathematics

EURO Summer Institute 2010
20th August – 4th September

Nonlinear methods such as semidefinite optimization or eigenvalue optimization have been successfully applied in the last decade to deal with NP-hard combinatorial optimization problems. A prominent example is furnished by the theta function, introduced by Lovasz (1979), which is a tractable graph parameter separating the clique number from the chromatic number. It can be formulated either in terms of eigenvalue optimization or as the optimal solution of a semidefinite program. Consequently, techniques from convex optimization are increasingly used in combinatorial optimization. On the algorithmic side, this is mostly due to the generalization of the interior-point methodology from linear to semidefinite programming. Even though the interior-point machinery carries over nicely from linear to semidefinite optimization, the computational overhead due to dense linear algebra operations makes it necessary to explore algorithmic alternatives to interior-point methods. The hyperplane rounding idea of Goemans and Williamson has turned out to be a strong theoretical tool in the approximation analysis of algorithms, opening up a new area of research in theoretical computer science. Finally, the new relaxations can also be used to solve problems to optimality. This requires algorithmic engineering to combine (nonlinear) bounding techniques with limited enumeration.

It is the purpose of the summer institute to focus on recent developments in this area. The following topics are of major interest to the ESI.

  • Nonlinear Methods in Combinatorial Optimization
  • Investigation of new relaxations for NP-hard problems,
  • Algorithms for large scale semidefinite programs and related other conical relaxations of combinatorial optimization problems,
  • Investigation of rounding heuristics, based on these relaxations,
  • Investigation of theoretical error estimates of these relaxations,
  • Exact solution methods, using semidefinite relaxations in combination with enumeration techniques