EURO Summer Institute 2010
Klagenfurt
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
|