An Algorithm For The κ-Level Uncapacitated Facility Location Problem

Variants of the facility location problem have been studied extensively in the operations research and management science literatures and have received considerable attention in the area of approximation algorithms. In the k- level uncapacitated facility location problem, we are given a set F of facilities, a set D of clients. The demand of each client is known, 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 facilities. There is a positive fixed cost of setting up a facility, and a per unit cost of shipping goods between each pair of locations. We assume that these distances are all nonnegative, symmetric 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.Since the uncapacitated facility location problem is NP-hard, approximation algorithms for NP-hard combinatorial optimization problems have proven to be a particularly successful way to generate excellent solutions for problems long considered intractable in practice. For the uncapacitated facility location problem, the first constant approximation algorithm was given by Shmoys. The algorithm was based on LP-rounding and the filtering technique proposed by Lin and Vitter and achieved an approximation factor of 3.16. This result was recently extended by Aardal, Chudak and Shmoys to a 3 - approximation algorithm for the k-level facility location problem.As the k -level uncapacitated facility location problem is NP-hard, much effort has been devoted to designing approximation algorithms for it. For many years, there is no still satisfactory method for the k- level uncapacitated facility location problem. So designing an effective algorithm in practice has become an important research topic in my thesis.In this paper we study the k - level uncapacitated facility location problem and the algorithms for solving the uncapacitated facility location problem. Inspired by these algorithms, we design a randomized rounding algorithm for the A:-level uncapacitated facility location problem. We can produce an optimal solution for the linear programming relaxation using the algorithm and then get the integral solution in the rounding step. We give an example of k = 2 in order to test the performance of the algorithm, the results of the example show that: 1. in the given example, with the number of clients and facilities increasing, the approximate ratio may increase, but overall not a big change, that is the approximate ratio and the total number of customers and facilities are not necessarily related; 2. the approximate ratio obtained by the algorithm is not more than 1.463 and the solution achieved by the algorithm is close to the optimum cost, at the same time our algorithm has a lower running time and improves the efficiency of the algorithm compared to the algorithm of Shmoys. So we can provide a better method for solving the A:-level uncapacitated facility location problems.