The seminar will focus on algorithmic and complexity aspects arising in the development of efficient solution techniques for computationally difficult optimization problems. A general technique for efficient approximation algorithms is to formulate an optimization problem as an integer linear program and then to relax the integrality conditions. Recently, there has been striking success in obtaining also approximation algorithms on more general mathematical programming such as semidefinite programming. In this and other context, randomization has proved to be a powerful algorithmic method: It yields to simple and easy to analyze algorithms for many optimization problems, and it leads to a better performance guarantee.

The seminar is intended to bring together researchers from different areas in combinatorial optimization and from applications. It will support the collaboration between researchers in computer science, mathematics and operations research.

The workshop will have the following aims:

• extending of randomization and semidefinite programming techniques to other optimization problems,
• improved approximation algorithms and structural insights by studying linear programming, semidefinite programming and randomization,
• development of approaches to solve (approximatively) large linear and semidefinite programs,
• complexity questions for randomization and semidefinite programming,
• practical implementation of the used techniques (randomization, semidefinite programming),
• exchange of informations on recent research and stimulation of further research.