  The fair $k$-median problem is one of the important clustering problems. The
current best approximation ratio is 4.675 for this problem with 1-fair
violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. As far as
we know, there is no available approximation algorithm for the problem without
any fair violation. In this paper, we consider the fair $k$-median problem in
bounded doubling metrics and general metrics. We provide the first QPTAS for
fair $k$-median problem in doubling metrics. Based on the split-tree
decomposition of doubling metrics, we present a dynamic programming process to
find the candidate centers, and apply min-cost max-flow method to deal with the
assignment of clients. Especially, for overcoming the difficulties caused by
the fair constraints, we construct an auxiliary graph and use minimum weighted
perfect matching to get part of the cost. For the fair $k$-median problem in
general metrics, we present an approximation algorithm with ratio $O(\log k)$,
which is based on the embedding of given space into tree metrics, and the
dynamic programming method. Our two approximation algorithms for the fair
$k$-median problem are the first results for the corresponding problems without
any fair violation, respectively.
