Approximation algorithms for facility location problems

Abstract

We present new approximation algorithms for several facility location problems. In each facility location problem that we study, there is a set of locations at which we may build a facility (such as a warehouse), where the cost of building at location i is f i ; furthermore, there is a set of client locations (such as stores) that require to be serviced by a facility, and if a client at location j is assigned to a facility at location i, a cost of c ij is incurred. The objective is to determine a set of locations at which to open facilities so as to minimize the total facility and assignment costs. In the uncapacitated case, each facility can service an unlimited number of clients, whereas in the capacitated case, each facility can serve, for example, at most u clients. These models and a number of closely related ones have been studied extensively in the Operations Research literature. We shall consider the case in which the assignment costs are symmetric and satisfy the triangle ineq...