Primal dual algorithms for Connected
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 Connected Facility Location problem.
We are given a graph G = (V,E) with costs c_e on the edges, a
set of facilities \F, and a set of demands or clients, \D. We
are also given a parameter M. A solution opens a set of facilities,
assigns each demand j to an open facility, and connects the open
facilities by a Steiner tree. The total cost incurred is the sum
of the facility opening costs, the client assignment costs and
M times the cost of the Steiner tree. We want a solution of minimum
cost. A special case is when all opening costs are 0 and facilities
opened anywhere, i.e., \F=V. If we know that a facility v is open
in the optimal solution, then this problem reduces to the rent-or-buy
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 the talk I will focus mainly on the
We also use our algorithm to get a constant-factor approximation
for the Connected k-Median problem.
Joint work with Amit Kumar and
appeared as "Primal-Dual Algorithms for
Connected Facility Location Problems", APPROX 2002,