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.
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.