CRPC-TR99784						January 1999

Title: A 3-approximation Algorithm for the k-level Uncapacitated Facility
Location Problem

Authors: Karen Aardal, Fabian A. Chudak, and David B. Shmoys

Submitted January 1999

Abstract:
	In the k-level uncapacitated facility location problem, we have a
set of demand points where clients are located. The demand of each client
is known. Facilities have to be located at given sites in order to service
the clients, and each client is to be serviced by a sequence of k 
different facilities, each of which belongs to a distinct level. There are
no capacity restrictions on the goods between each pair of locations. We
assume that these distances are all nonnegative and satisfy the triangle
inequality. The problem is to find an assignment of each client to a
sequence of k facilities, one at each level, so that the demand of each
client is satisfied, for which the sum of the setup costs and the service
costs is minimized.
	We develop a randomized algorithm for the k-level facility
locatino problem that is guaranteed to find a feasible solution of
expected cost within a factor of 3 of the optimum cost. THe algorithm is a
randomized rounding procedure that uses an optimal solution of a linear
programming relaxation and its dual toake a random choice of facilities to
be opened. We show how this algorithm can be derandomized to yield a
3-approximation algorithm.

------------------------------------------------------------------------------
Karen Aardal
aardal@cs.uu.nl
Department of Computer Science
Utrecht University

Fabian A. Chudak
chudak@cs.cornell.edu
IBM TJ Watson Research Center

David B. Shmoys
shmoys@cs.cornell.edu
School of Operations Research & Industrial Engineering
Cornell University