IDSIA Seminars

IDSIA Seminars

Dr. Thomas Rothvoss - An improved LP-based approximation for the Steiner tree problem

The Steiner tree problem is one of the most fundamental NP-hard problems:

given a weighted undirected graph G=(V,E) and a subset of terminal nodes, find a minimum weight tree spanning the terminals.

In this talk, we introduce a directed LP relaxation and describe an approximation algorithm based on iterative randomized rounding of a fractional solution.

We prove an approximation guarantee of 1.39 for the algorithm (improving over the previously best known factor of 1.55) and show that the mentioned LP has an integrality gap of at most 1.55 (improving over the previously best known factor of 2).

20 luglio 2010 11:15