CS 789 THEORY SEMINAR [home]

Speaker:  Chaitanya Swamy   
Affiliation: Computer Science, Cornell University
Date: Monday, April 8, 2002
Title: Fault Tolerant Facility Location

Abstract: 

We consider a fault tolerant generalization of the classical uncapacitated facility location problem. We are given a set of facilties and a set of clients. There are facility costs fi and connection costs cij between facility i and client j. The goal is to open facilities and connect clients to facilities so that each client is connected to rj distinct facilities while minimizing the total facility opening cost and connection cost. We consider the case where the cij s form a metric. We give a 2.075-approximation algorithm for this problem which is currently the best known ratio. Recently Guha et al.(2001) gave a constant-factor approximation algorithm by rounding the optimal solution of an LP extending the filtering and decomposition technique of Shmoys, Tardos & Aardal(1997). Our algorithm is also based on LP rounding, but we do not use filtering. Instead we explicitly use properties of the primal and dual optimal solutions and use a clustered randomized rounding approach similar in spirit to Chudak and Shmoys(1998). A technical difficulty that we need to overcome is the presence of negative terms in the dual objective function which makes it difficult to bound the cost in terms of the dual variables. In this talk I will present first a simple deterministic 4-approximation algorithm and then show how randomization can improve the ratio to 2+2/e.

We also consider the k-median version of the above problem where we do not have facility costs but require that only k facilities be opened. We give the first constant-factor approximation algorithm for this problem for the special case where all the requirements are the same.