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.

[top]