TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 00041

Linear, Semidefinite Programming and Randomization Methods for Combinatorial Optimization Problems

( Jan 23 – Jan 28, 2000 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/00041

Organizers
  • J. Rolim (Geneva)
  • K. Jansen (Kiel)
  • M. Sudan (MIT Cambridge)



Motivation

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.

Participants
  • J. Rolim (Geneva)
  • K. Jansen (Kiel)
  • M. Sudan (MIT Cambridge)