LP-based Approximation Algorithms for Capacitated Facility Location

Abstract

There has been a great deal of recent work on approximation algorithms for facility location problems [9]. We consider the capacitated facility location problem with hard capacities. We are given a set of facilities, ${\mathcal F}$, and a set of clients ${\mathcal D}$ in a common metric space. Each facility i has a facility opening costf _i and capacityu _i that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set ${\mathcal F}$ and assign each client to an open facility so that at most u _i clients are assigned to any open facility i. The cost of assigning client j to facility i is given by their distance c _ij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs.