Lectures and Colloquia during the semester

Montag, den 18. Dezember 2000

Freie Universität Berlin - Institut für Informatik
Takustraße 9, 14195 Berlin
Seminarraum 005

Lecture - 14.00 Uhr c.t.

Günter Rote - Freie Universität Berlin

The integrality gap of the semidefinite programming relaxation for the maximum cut problem

Abstract: Feige and Schechtman have recently shown that the ratio between the maximum cut and its semidefinite programming relaxation can be as large as 0.878, the same bound as the approximation ratio of the Goemans-Williamson algorithm. After reviewing the semidefinite programming relaxation and Goemans and Williamson's randomized rounding approach, I will present the examples that have a large gap. Their construction is based on a very simple geometric idea, but the proof employs techniques drawn from other fields such as convex geometry. I will also review some related results, such as Karloff's examples which exhibit a bad approximation ratio.

Colloquium - 16 Uhr s.t.

Stefan Hougardy - Humboldt-Universität zu Berlin

Approximation Algorithms for the Steiner Tree Problem

Abstract: The Steiner tree problem asks for a shortest network connecting a given subset of the vertices of a graph. This problem is known to be APX-complete, i.e., we do not expect to have polynomial time approximation schemes as it is the case for the euclidean Steiner tree problem. The gap between upper and lower bounds for the best approximation ratio for the Steiner tree problem is currently still quite large. We present some recent results on narrowing this gap.