  In this paper, we consider the fault-tolerant $k$-median problem and give the
\emph{first} constant factor approximation algorithm for it. In the
fault-tolerant generalization of classical $k$-median problem, each client $j$
needs to be assigned to at least $r_j \ge 1$ distinct open facilities. The
service cost of $j$ is the sum of its distances to the $r_j$ facilities, and
the $k$-median constraint restricts the number of open facilities to at most
$k$. Previously, a constant factor was known only for the special case when all
$r_j$s are the same, and a logarithmic approximation ratio for the general
case. In addition, we present the first polynomial time algorithm for the
fault-tolerant $k$-median problem on a path or a HST by showing that the
corresponding LP always has an integral optimal solution.
  We also consider the fault-tolerant facility location problem, where the
service cost of $j$ can be a weighted sum of its distance to the $r_j$
facilities. We give a simple constant factor approximation algorithm,
generalizing several previous results which only work for nonincreasing weight
vectors.
