Thomas Rothvoß

Title:
An improved bound for the random sampling algorithm for connected facility location

Abstract:
The connected facility location problem is the following. We
are given a graph G=(V,E) weighted with a function c: V --> |R,
a parameter M >= 1 and a subset D of nodes, which are called demands.
The task is to buy or rent edges such that all demands can
communicate to each other at the same time. Renting an edges e costs
c(e) per needed capacity while buying e costs M*c(e), independent from the capacity.

In 2003 Gupta, Kumar and Kleinberg gave a very simple approximation
algorithm for this problem, based an random sampling, which attracted
much attention in recent literature. They were able to show an approximation
ratio of 3.55. In my talk I will show how to improve this bound
to 3.05 and I will give a sketch, how to do further improvements
to a ratio of 2.92 using flow cancelation arguments.

This is joint work with Fritz Eisenbrand and Fabrizio Grandoni.