  We consider the $k$-Median problem on planar graphs: given an edge-weighted
planar graph $G$, a set of clients $C \subseteq V(G)$, a set of facilities $F
\subseteq V(G)$, and an integer parameter $k$, the task is to find a set of at
most $k$ facilities whose opening minimizes the total connection cost of
clients, where each client contributes to the cost with the distance to the
closest open facility. We give two new approximation schemes for this problem:
-- FPT Approximation Scheme: for any $\epsilon>0$, in time
$2^{O(k\epsilon^{-3}\log (k\epsilon^{-1}))}\cdot n^{O(1)}$ we can compute a
solution that
  (1) has connection cost at most $(1+\epsilon)$ times the optimum, with high
probability. -- Efficient Bicriteria Approximation Scheme: for any
$\epsilon>0$, in time $2^{O(\epsilon^{-5}\log (\epsilon^{-1}))}\cdot n^{O(1)}$
we can compute a set of at most $(1+\epsilon)k$ facilities
  (2) whose opening yields connection cost at most $(1+\epsilon)$ times the
optimum connection cost for opening at most $k$ facilities, with high
probability.
  As a direct corollary of the second result we obtain an EPTAS for the Uniform
Facility Location on planar graphs, with same running time.
  Our main technical tool is a new construction of a "coreset for facilities"
for $k$-Median in planar graphs: we show that in polynomial time one can
compute a subset of facilities $F_0\subseteq F$ of size $k\cdot (\log
n/\epsilon)^{O(\epsilon^{-3})}$ with a guarantee that there is a
$(1+\epsilon)$-approximate solution contained in $F_0$.
