CS 789 THEORY SEMINAR [home]

Speaker:     Zoya Svitkina, Cornell University
Date:          November 7, 2005
Title:          Approximation algorithm for facility location with hierarchical facility costs

Abstract:
We consider the facility location problem in which the cost of a facility depends on the set of clients using that facility. As a result, unlike in traditional facility location problems, the difficult question is not which facilities should be opened, but instead which clients should be assigned to which facilities. The facility cost function is hierarchical in the sense that it can be represented by a tree structure and the total cost is the sum of costs incurred at different levels of this "cost tree". The hierarchical facility cost function models multilevel service installation costs. Shmoys, Swamy and Levi (2004) gave an approximation algorithm for a problem with two levels of costs. Here we consider the setting with arbitrary number of levels, and present a 5-approximation algorithm for any number of levels.

Our algorithm is based on a local search technique, and uses two types of local improvement moves: aggregate and disperse. We show that a locally optimal solution is within a factor 5 of optimal by arguing that: (1) whenever no improving aggregate move exists, the connection cost of the solution cannot be very big, and (2) whenever no improving disperse move exists, the facility cost of the current solution cannot be very big. In addition, we show that each of these local improvement moves can be implemented to run in polynomial time.

This is joint work with Eva Tardos and will appear in SODA 2006.