Approximation algorithms for the capacitated k-facility location problems

We consider the capacitated $k$-facility location problem, in which we are given a set of clients with demands, a set of facilities with capacities and a constant number $k$. It costs $f_i$ to open facility $i$, and it costs $c_{ij}$ for facility $i$ to serve one unit of demand from client $j$. The objective is to open at most $k$ facilities serving all the demands and satisfying the capacity constraints while minimizing the sum of service and opening costs. Firstly, we give the first constant factor approximation algorithm for the single-sink capacitated $k$-facility location problem, which uses an iterative LP-rounding procedure and achieves an approximation guarantee of $2$. Secondly, we show that the capacitated $k$-facility location problem with uniform capacities is solvable in polynomial time if the number of clients is fixed by reducing it to a collection of {the transportation problems.} Thirdly, we design a simple $(7+\epsilon)$-approximation algorithm for the capacitated $k$-facility location problem with nonuniform capacities using at most $2k+1$ facilities. In addition, our algorithms also work for the capacitated $k$-median problems which are special cases of the capacitated $k$-facility location problems.