Improved approximation algorithms for a capacitated facility location problem

Abstract

Algorithms for the metric variant of the capacitated facility location problem is investigated. The goal is to determine the number of facilities to install at each potential facility location and an assignment of each client to these facilities so as to minimize the overall total cost. The main result is a 3-approximation algorithm for the problem considered, improving on a 5.69-approximation algorithm.