CS 789 THEORY SEMINAR [home]

Speaker:  Chaitanya Swamy
Affiliation:  Cornell University, Computer Science
Date: Monday, October 28, 2002
Title: Primal dual algorithms for Connected Facility Location

Abstract:

Consider a setting where we have some facilities and demand points. We want to open facilities, assign each demand point to an open facility, and further connect the open facilities by a Steiner tree. The tree allows the open facilities 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 the 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 a facility v 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 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.