Connected Facility Location

Consider a setting where we have some facilities and demand points. We
want to open facillities, assign each demand point to an open
facility, and further connect the open facilities by a Steiner tree.
The tree allows the open facillities to communicate easily with each
other. This is the {\em Connected Facility Location} problem. We are given
a graph $G = (V,E)$ with cost $c_e$ on edge $e$, a set of facilities $\F
\subseteq V$, and a set of demands $\D \subseteq V$. We are also given a
parameter $M\geq 1$. A solution opens a set $A$ of facilities, assigns
each demand $j$ to an open facility $i(j)$, and connects the open
facilities by a Steiner tree $T$. The total cost incurred is

$\sum_{i\in A} f_i + \sum_{j\in\D} c_{i(j)j} + M\sum_{e\in T} c_e$.

We want a solution of minimum cost.
A special case is when all opening costs are 0 and facilities may be
opened anywhere, i.e., $\F=V$. If we {\em know} a facility $v$ that is open,
then this problem reduces to the {\em rent-or-buy} problem.

We give the first primal-dual algorithms for these problems and achieve
the best known approximation guarantees. We give a 9-approx. algorithm for
connected facility location and a 5-approx. for the rent-or-buy problem.
In this talk I will focus mainly on the rent-or-buy problem.
We also use our algorithm to get a constant-factor approximation for the
connected $k$-median problem.