A 3-approximation algorithm for the k-level uncapacitated facility location problem

In the k-level uncapacitated facility location problem, we have a set of de mand 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 client s, and each client is to be serviced by a sequence of k different facilitie s, each of which belongs to a distinct level. There are no capacity restric tions on the facilities. There is a positive fixed cost of setting up a fac ility, and a per unit cost of shipping goods between each pair of locations . We assume that these distances are all nonnegative and satisfy the triang le inequality. The problem is to find an assignment of each client to a seq uence 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 i s minimized. We develop a randomized algorithm for the k-level facility location problem that is guaranteed to find a feasible solution of expected cost within a f actor of 3 of the optimum cost. The algorithm is a randomized rounding proc edure that uses an optimal solution of a linear programming relaxation and its dual to make a random choice of facilities to be opened. We show how th is algorithm can be derandomized to yield a 3-approximation algorithm. (C) 1999 Elsevier Science B.V. All rights reserved.