Primal dual algorithms for Connected Facility Location
Chaitanya Swamy

Abstract:

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 may be
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 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 the 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.

Joint work with Amit Kumar and appeared as "Primal-Dual Algorithms for Connected Facility Location Problems", APPROX 2002, pages 256-269.