Approximation algorithms for facility location problems (extended abstract)

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 ~i; ftiermore, 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 cl] is incurred that is proportional to the distance between i and j. 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 incapacitated 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.