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.