  We study 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 $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.
  In this paper, we give the first fully polynomial time approximation scheme
(FPTAS) for the single-sink (single-client) capacitated $k$-facility location
problem. Then, 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 transportation problems. Third, we
analyze the structure of extreme point solutions, and examine the efficiency of
this structure in designing approximation algorithms for capacitated
$k$-facility location problems. Finally, we extend our results to obtain an
improved approximation algorithm for the capacitated facility location problem
with uniform opening cost.
