CENTER Carnegie Mellon UniversityCarnegie Mellon Computer Science DepartmentSchool of Computer Science
Integrated Logistics Workshop
Related Activities
Outreach Roadshow

Primal dual algorithms for Connected Facility Location
Chaitanya Swamy


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.

This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation