Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 24, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Christian Balderer
In the Connected Facility Location problem, we are given an undirected graph with edge costs and a subset D of the vertices, called the demands. The task is to open a set of connected facilities such that the sum of all shortest-path distances from a demand to its closest facility plus the cost for connecting the facilities is minimized.
We present a simple randomized approximation algorithm that achieves a factor 3.55 approxmiation, which is an improvement over the previously known bound of 4.55.
Automatic MiSe System Software Version 1.4803M | admin login