$\text{cost}(G_{close,\tilde{\mathcal{S}}},\tilde{\mathcal{S}})\leq(1+\varepsilon)\text{cost}(G_{close,\tilde{\mathcal{S}}},\mathcal{S})+\varepsilon\text{cost}(G,\mathcal{A})$.
Hence:

$\displaystyle|\text{cost}(G_{close,\tilde{\mathcal{S}}},\mathcal{S})-\text{cost}(\Omega\cap
G_{close,\tilde{\mathcal{S}}},\mathcal{S})|$ $\displaystyle\leq~{}$
$\displaystyle|\text{cost}(G_{close,\tilde{\mathcal{S}}},\tilde{\mathcal{S}})-\text{cost}(\Omega\cap
G_{close,\tilde{\mathcal{S}}},\tilde{\mathcal{S}})|$
$\displaystyle\qquad+\frac{\varepsilon}{z\log
z/\varepsilon}(\text{cost}(G_{close,\tilde{\mathcal{S}}},\mathcal{S})+\text{cost}(G_{close,\tilde{\mathcal{S}}},\mathcal{A}))$
$\displaystyle\qquad+\frac{\varepsilon}{z\log
z/\varepsilon}(\text{cost}(G_{close,\tilde{\mathcal{S}}}\cap\Omega,\mathcal{S})+\text{cost}(G_{close,\tilde{\mathcal{S}}}\cap\Omega,\mathcal{A}))$
$\displaystyle\leq~{}$ $\displaystyle\frac{O(\varepsilon)}{z\log
z/\varepsilon}\left(\text{cost}(G,\mathcal{A})+\text{cost}(G,\mathcal{S})\right)$
$\displaystyle\qquad+\frac{\varepsilon}{z\log
z/\varepsilon}(\text{cost}(G_{close,\tilde{\mathcal{S}}}\cap\Omega,\mathcal{S})+\text{cost}(G_{close,\tilde{\mathcal{S}}}\cap\Omega,\mathcal{A}))$

We now deal with the other far points. For this, note that $G\setminus
G_{close,\tilde{\mathcal{S}}}\subseteq G_{far,\mathcal{S}}$. Indeed, any point
$p\in G\setminus G_{far,\mathcal{S}}$ has its cost preserved by
$\tilde{\mathcal{S}}$, and therefore verifies

$\displaystyle\text{cost}(p,\tilde{\mathcal{S}})$
$\displaystyle\leq(1+\frac{\varepsilon}{z\log
z/\varepsilon})\text{cost}(p,\mathcal{S})+\frac{\varepsilon}{z\log
z/\varepsilon}\text{cost}(p,\mathcal{A})$
$\displaystyle\leq(1+\varepsilon)\cdot
4^{z}\text{cost}(p,\mathcal{A})+\varepsilon\text{cost}(p,\mathcal{A})\leq
5^{z}\text{cost}(p,\mathcal{A}).$

Consequently, $G\setminus G_{far,\mathcal{S}}\subseteq
G_{close,\tilde{\mathcal{S}}}$, which implies $G\setminus
G_{close,\tilde{\mathcal{S}}}\subseteq G_{far,\mathcal{S}}$. Hence, we can use
Lemma 15:

$\displaystyle|\text{cost}(G\setminus
G_{close,\tilde{\mathcal{S}}},\mathcal{S})-\text{cost}(\Omega\cap(G\setminus
G_{close,\tilde{\mathcal{S}}}),\mathcal{S})|$ $\displaystyle\leq~{}$
$\displaystyle\text{cost}(G\setminus
G_{close,\tilde{\mathcal{S}}},\mathcal{S})+\text{cost}(\Omega\cap(G\setminus
G_{close,\tilde{\mathcal{S}}}),\mathcal{S})$ $\displaystyle\leq~{}$
$\displaystyle\text{cost}(G_{far,\mathcal{S}},\mathcal{S})+\text{cost}(\Omega\cap
G_{far,\mathcal{S}},\mathcal{S})$ $\displaystyle\leq~{}$
$\displaystyle\frac{\varepsilon}{z\log
z/\varepsilon}\cdot\text{cost}(\mathcal{S}).$

Hence, adding the two inequalities gives that

$\displaystyle|\text{cost}(G,\mathcal{S})-\text{cost}(\Omega\cap
G,\mathcal{S})|$ $\displaystyle\leq$ $\displaystyle\frac{O(\varepsilon)}{z\log
z/\varepsilon}\cdot\text{cost}(\mathcal{S})+\frac{\varepsilon}{z\log
z/\varepsilon}(\text{cost}(G\cap\Omega,\mathcal{S})+\text{cost}(G\cap\Omega,\mathcal{A})).$

To remove the terms depending on $\Omega$ from the right hand side, one can
proceed as in the end of Lemma 2, applying grossly the previous inequality to
get $\text{cost}(G\cap\Omega,\mathcal{S})=O(1)\text{cost}(\mathcal{S})$ and
$\text{cost}(G\cap\Omega,\mathcal{A})=O(1)\text{cost}(\mathcal{A})$. This
concludes the theorem:

$\displaystyle|\text{cost}(G,\mathcal{S})-\text{cost}(\Omega\cap
G,\mathcal{S})|\leq\frac{O(\varepsilon)}{z\log
z/\varepsilon}\cdot(\text{cost}(G,\mathcal{S})+\text{cost}(G,\mathcal{A})).$

∎

This concludes the coreset construction for the outer groups.

##  7 Partitioning into Well Structured Groups

In this section, we show that the outcome of the partitioning step satisfies
Lemma 4, that we restate for convenience.

See 4

Recall that the inner ring $R_{I}(C)$ (resp. outer ring $R_{O}(C)$) of a
cluster $C$ consists of the points of $C$ with cost at most
$\left(\nicefrac{{\varepsilon}}{{z}}\right)^{2z}\Delta_{C}$ (resp. at least
$\left(\nicefrac{{z}}{{\varepsilon}}\right)^{2z}\Delta_{C}$). The main ring
$R_{M}(C)$ consist of all the other points of $C$.

Recall also that $\mathcal{D}$ contains all points that are either in some
inner ring, in some group $G_{j,min}$ or in $G^{O}_{min}$. $P_{1}$ contains
center of $\mathcal{A}$ weighted by the number of points from $\mathcal{D}$ in
their clusters.

To prove Lemma 4, we treat separately the inner ring and the groups
$G_{j,min}$ and $G^{O}_{min}$ in the next two lemmas. Their proof are deferred
to next sections. For all those lemmas, we fix a metric space $I$ a set of
clients $P$, two positive integers $k$ and $z$, and
$\varepsilon\in\mathbb{R}^{*}_{+}$. We also fix $\mathcal{A}$, a solution to
$(k,z)$-clustering on $P$ with cost $\text{cost}(\mathcal{A})\leq
c_{\mathcal{A}}\text{cost}(\text{OPT})$.

######  Lemma 16.

For any solution $\mathcal{S}$ and any cluster $C$ with center $c$ of
$\mathcal{A}$,

$\displaystyle\left|\text{cost}(R_{I}(C),\mathcal{S})-|R_{I}(C)|\cdot\text{cost}(c,\mathcal{S})\right|\leq\varepsilon(\text{cost}(C,\mathcal{A})+\text{cost}(R_{I}(C),\mathcal{S})).$

######  Lemma 17.

For any solution $\mathcal{S}$ and any $j$,

$\displaystyle\left|\text{cost}(G_{j,min},\mathcal{S})-\sum_{i=1}^{k}|C_{i}\cap
G_{j,min}|\cdot\text{cost}(c_{i},\mathcal{S})\right|\leq\varepsilon\cdot\text{cost}(R_{j},\mathcal{S})+\varepsilon\cdot\text{cost}(R_{j},\mathcal{A}).$

Moreover, for any solution $\mathcal{S}$,

$\displaystyle\left|\text{cost}(G^{O}_{min},\mathcal{S})-\sum_{i=1}^{k}|C_{i}\cap
G^{O}_{min}|\cdot\text{cost}(c_{i},\mathcal{S})\right|\leq\varepsilon\cdot\text{cost}(\mathcal{S})+\varepsilon\cdot\text{cost}(\mathcal{A}).$

The proof of Lemma 4 combines those lemmas.

###### Proof of Lemma 4.

We decompose
$|\text{cost}(\mathcal{D},\mathcal{S})-\text{cost}(P_{1},\mathcal{S})|$ into
terms corresponding to the previous lemmas:

$\displaystyle|\text{cost}(\mathcal{D},\mathcal{S})-\text{cost}(P_{1},\mathcal{S})|$
$\displaystyle\leq\sum_{i=1}^{k}\left|\text{cost}(R_{I}(C_{i}),\mathcal{S})-|R_{I}(C_{i})|\text{cost}(c_{i},\mathcal{S})\right|$
$\displaystyle\quad+\sum_{j=2z\log(\varepsilon/z)}^{2z\log(z/\varepsilon)}\left|\text{cost}(G_{j,min},\mathcal{S})-\sum_{i=1}^{k}|C_{i}\cap
G_{j,min}|\text{cost}(c_{i},\mathcal{S})\right|$
$\displaystyle\quad+\left|\text{cost}(G^{O}_{min},\mathcal{S})-\sum_{i=1}^{k}|C_{i}\cap
G^{O}_{min}|\text{cost}(c_{i},\mathcal{S})\right|$
$\displaystyle\leq\sum_{i=1}^{k}\varepsilon(\text{cost}(C_{i},\mathcal{A})+\text{cost}(R_{I}(C_{i}),\mathcal{S}))$
$\displaystyle\quad+2\varepsilon\text{cost}(\mathcal{S})+2\varepsilon\text{cost}(\mathcal{A})+\varepsilon(\text{cost}(\mathcal{S})+\text{cost}(\mathcal{A}))$
$\displaystyle\leq 8\varepsilon c_{\mathcal{A}}\text{cost}(\mathcal{S}),$

where the second inequality uses Lemmas 16 and 17.

∎

###  7.1 The Inner Ring: Proof of Lemma 16

See 16

###### Proof.

Let $C$ be a cluster induced by $\mathcal{A}$, and $p$ be a point in the inner
ring $R_{I}(C)$. We start by bounding
$|\text{cost}(p,\mathcal{S})-\text{cost}(c,\mathcal{S})|$. Let
$\mathcal{S}(p)$ (resp. $\mathcal{S}(c)$) be the closest point from
$\mathcal{S}$ to $p$ (resp. $c$).

Using Lemma 1, we get

$|\text{cost}(p,\mathcal{S})-\text{cost}(c,\mathcal{S})|\leq\varepsilon\cdot\text{cost}(p,\mathcal{S})+(1+2z/\varepsilon)^{z-1}\cdot\text{cost}(c,p).$

Since $p$ is from the inner ring of its cluster,
$\text{cost}(c,p)\leq\left(\frac{\varepsilon}{z}\right)^{2z}\Delta_{C}$, hence
$(1+2z/\varepsilon)^{z-1}\text{cost}(c,p)\leq(2+\varepsilon)^{z-1}\cdot(\varepsilon/z)^{z+1}\cdot\Delta_{C}\leq\varepsilon\Delta_{C}$,
for small enough $\varepsilon$.

Summing this over all points of the inner ring yields

$\displaystyle\left|\text{cost}(R_{I}(C),\mathcal{S})-|R_{I}(C)|\cdot\text{cost}(c,\mathcal{S})\right|$
$\displaystyle\leq\sum_{p\in
R_{I}(C)}|\text{cost}(p,\mathcal{S})-\text{cost}(c,\mathcal{S})|$
$\displaystyle\leq\sum_{p\in
R_{I}(C)}\varepsilon\text{cost}(p,\mathcal{S})+\varepsilon\Delta_{C}$
$\displaystyle\leq\varepsilon\text{cost}(R_{I}(C),\mathcal{S})+\varepsilon|R_{I}(C)|\Delta_{C}$
$\displaystyle\leq\varepsilon\text{cost}(R_{I}(C),\mathcal{S})+\varepsilon\text{cost}(C,\mathcal{A})$

This implies

$\left|\text{cost}(R_{I}(C),\mathcal{S})-|R_{I}(C)|\cdot\text{cost}(c,\mathcal{S})\right|\leq\varepsilon(\text{cost}(C,\mathcal{A})+\text{cost}(R_{I}(C),\mathcal{S})).$

∎

###  7.2 The Cheap Groups: Proof of Lemma 17

See 17

###### Proof.

Using Lemma 1, for a point $p$ in cluster $C_{i}$

$\left|\text{cost}(c_{i},\mathcal{S})-\text{cost}(p,\mathcal{S})\right|\leq\varepsilon\text{cost}(p,\mathcal{S})+\left(1+\frac{2z}{\varepsilon}\right)^{z-1}\text{cost}(p,c_{i}).$

Let $G$ be a group, either $G_{j,min}$ or $G^{O}_{min}$. Summing for all
cluster $C_{i}$ and all $p\in G\cap C_{i}$, we now get

$\displaystyle\left|\sum_{i=1}^{k}|C_{i}\cap
G|\cdot\text{cost}(c_{i},\mathcal{S})-\text{cost}(G,\mathcal{S})\right|$
$\displaystyle\leq$
$\displaystyle\varepsilon\cdot\text{cost}(G,\mathcal{S})+\sum_{i=1}^{k}\sum_{p\in
G\cap
C_{i}}\left(1+\frac{2z}{\varepsilon}\right)^{z-1}\text{cost}(p,\mathcal{A})$
$\displaystyle\leq$
$\displaystyle\varepsilon\cdot\text{cost}(G,\mathcal{S})+\sum_{i=1}^{k}\left(\frac{3z}{\varepsilon}\right)^{z-1}\text{cost}(C_{i}\cap
G,\mathcal{A})$ $\displaystyle\leq$
$\displaystyle\varepsilon\cdot\text{cost}(G,\mathcal{S})+\left(\frac{3z}{\varepsilon}\right)^{z-1}\text{cost}(G,\mathcal{A})$

Now, either $G=G_{j,min}$ for some $j$, and
$\text{cost}(G,\mathcal{A})\leq\left(\frac{\varepsilon}{4z}\right)^{z}\cdot\text{cost}(R_{j},\mathcal{A})$;
or $G=G^{O}_{min}$, and
$\text{cost}(G,\mathcal{A})\leq\left(\frac{\varepsilon}{4z}\right)^{z}\cdot\text{cost}(R_{O}(\mathcal{A}),\mathcal{A})\leq\left(\frac{\varepsilon}{4z}\right)^{z}\cdot\text{cost}(\mathcal{A})$.

In both cases, the lemma follows. ∎

##  8 Application of the Framework: New Coreset Bounds for Various Metric
Spaces

In this section, we apply the coreset framework to specifics metric spaces.
For each of them, we show the existence of a small approximate centroid set,
and apply Theorem 1 to prove the existence of small coresets.

We recall the definition of a centroid set (Definition 1): given an instance
of $(k,z)$-clustering and a set of centers $\mathcal{A}$, an
$\mathcal{A}$-approximate centroid set $\mathbb{C}$ is a set that satisfies
the following: for every solution $\mathcal{S}$, there exists
$\tilde{\mathcal{S}}\in\mathbb{C}^{k}$ such that for all points $p$ that
verifies
$\text{cost}(p,\mathcal{S})\leq\left(\frac{8z}{\varepsilon}\right)^{z}\text{cost}(p,\mathcal{A})$
or
$\text{cost}(p,\tilde{\mathcal{S}})\leq\left(\frac{8z}{\varepsilon}\right)^{z}\text{cost}(p,\mathcal{A})$,
it holds
$|\text{cost}(p,\mathcal{S})-\text{cost}(p,\tilde{\mathcal{S}})|\leq\frac{\varepsilon}{z\log(z/\varepsilon)}\left(\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{A})\right)$.

Theorem 1 states that in case there is an $\mathcal{A}$-approximate centroid
set $\mathbb{C}$, then there is a linear-time algorithm that constructs with
probability $1-\pi$ a coreset of size

$O\left(\frac{2^{O(z\log
z)}\cdot\log^{4}1/\varepsilon}{\min(\varepsilon^{2},\varepsilon^{z})}\left(k\log|\mathbb{C}|+\log\log(1/\varepsilon)+\log(1/\pi)\right)\right)$

###  8.1 Structural Property on Solutions

We also show a structural property on solutions, that we will use in order to
show the existence of small approximate centroid sets. Essentially, when
replacing a center $s$ by a center in $\mathbb{C}$ we will make an error
$\varepsilon\text{cost}(q,\mathcal{A})$ for some $q$ that we can choose: it is
necessary to ensure this error is tiny compared to any
$\text{cost}(p,s)+\text{cost}(p,\mathcal{A})$.

Given a point $q$ and a center $s$, we say that a point $p$ is _problematic_
with respect to $q$ and $s$ when
$\text{dist}(p,\mathcal{A})+\text{dist}(p,s)\leq\frac{\varepsilon^{2}}{8z^{2}}(\text{dist}(q,\mathcal{A})+\text{dist}(q,s))$.
In that case, we cannot bound the error
$\text{dist}(q,\mathcal{A})+\text{dist}(q,s)$ by some quantity depending on
$\text{cost}(p,s)+\text{cost}(p,\mathcal{A})$. However, we show the following:

######  Lemma 18.

Let $\mathcal{S}$ be a solution, such that any input point $p$ verifies
$\text{dist}(p,\mathcal{S})\leq\frac{8z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$.
There exists a solution $\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such that

  * •

for all $p$, it holds that
$|\text{cost}(p,\mathcal{S})-\text{cost}(p,\mathcal{S}^{\prime})|\leq\frac{\varepsilon}{z\log
z/\varepsilon}(\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{A}))$, and

  * •

for any center $s\in\mathcal{S}^{\prime}$, let
$q=\text{argmin}_{p:\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})}\text{dist}(p,\mathcal{A})+\text{dist}(p,s)$.
There is no problematic point with respect to $q$ and $s$.

###### Proof.

First, we show that in case there is a problematic point $p$ with respect to
some $s$ and $q$, then we can serve the whole cluster of $s$ by
$\mathcal{S}(p)$, the point that serves $p$ in $\mathcal{S}$. We work in this
proof with particular solutions, where points are not necessarily assigned to
their closest center. This simplifies the proof, but needs particular care at
some moments. In particular, we will ensure that
$\text{dist}(p,\mathcal{S}(p))\leq\frac{10z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$
is always verified. We will then remove inductively centers with problematic
points to construct $\mathcal{S}^{\prime}$.

Removing a center that has a problematic point.
Let $s\in\mathcal{S}$, and
$q=\text{argmin}_{p:\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})}\text{dist}(p,\mathcal{A})+\text{dist}(p,s)$
as in the statement. Let $p$ be a problematic point with respect $s$ and $q$,
and $\mathcal{S}(p)$ its the center serving $p$ in $\mathcal{S}$. First, note
that since $p$ is problematic, it must be that
$\text{dist}(p,\mathcal{S}(p))\leq\text{dist}(s,p)$: otherwise, $p$ would
verify
$\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})$, and
the minimality of $q$ would ensure that $p$ is not problematic. Thus, it holds
that:

$\displaystyle\text{dist}(s,\mathcal{S}(p))$
$\displaystyle\leq\text{dist}(s,p)+\text{dist}(p,\mathcal{S}(p))\leq
2\text{dist}(s,p)$ $\displaystyle\leq
2(\text{dist}(s,p)+\text{dist}(p,\mathcal{A}))\leq\frac{\varepsilon^{2}}{4z^{2}}(\text{dist}(q,\mathcal{A})+\text{dist}(q,s)).$

Now, let $p^{\prime}$ be served by $s$. Using the triangle inequality, we
immediately get

$\displaystyle\text{dist}(p^{\prime},\mathcal{S}(p))\leq\text{dist}(p^{\prime},s)+\text{dist}(s,\mathcal{S}(p))\leq\text{dist}(p^{\prime},s)+\frac{\varepsilon^{2}}{4z^{2}}(\text{dist}(q,\mathcal{A})+\text{dist}(q,s)).$

Additionally, it holds that

$\displaystyle\min_{q^{\prime}:\text{dist}(q^{\prime},\mathcal{S}(p))\leq\frac{10z}{\varepsilon}\text{dist}(q^{\prime},\mathcal{A})}\text{dist}(q^{\prime},\mathcal{A})+\text{dist}(q^{\prime},\mathcal{S}(p))$
$\displaystyle\leq\text{dist}(p,\mathcal{S}(p))+\text{dist}(p,\mathcal{A})$
$\displaystyle\leq\text{dist}(s,p)+\text{dist}(p,\mathcal{A})$
$\displaystyle\leq\frac{\varepsilon^{2}}{8z^{2}}(\text{dist}(q,\mathcal{A})+\text{dist}(q,s))$
(27)

Hence, if $\mathcal{S}(p)$ is removed as well, the error for points served by
$s$ will be an $\frac{\varepsilon^{2}}{8z^{2}}$-fraction of the initial error.
This implies that the total error will not accumulate, as we will now see.

Constructing $\mathcal{S}^{\prime}$. To construct $\mathcal{S}^{\prime}$, we
proceed iteratively: start with $\mathcal{S}^{\prime}=\mathcal{S}$, and as
long as there exists a center $s$ that have a problematic point $p$ with
respect to it, remove $s$ and reassign the whole cluster of $s$ to
$\mathcal{S}^{\prime}(p)$, the closest point to $p$ in the current solution.
This process must end, as there is no problematic point when there is a single
center.

For a point $p$, let $s_{1},...,s_{j}$ be the successive cluster it is
reassigned to, with corresponding $q_{1},...,q_{j}$. Using Eq. 27, it holds
that
$\text{dist}(q_{i+1},\mathcal{A})+\text{dist}(q_{i+1},s_{i+1})\leq\frac{\varepsilon^{2}}{8z^{2}}(\text{dist}(q_{i},\mathcal{A})+\text{dist}(q_{i},s_{i}))$.
Hence, the distance increase for $p$ is geometric: using that
$\text{dist}(q_{1},\mathcal{A})+\text{dist}(q_{1},s_{1})\leq\text{dist}(p,\mathcal{A})+\text{dist}(p,\mathcal{S})$
(which holds by minimality of $q_{1}$), we get that at any given step $i$ it
holds that

$\displaystyle\text{dist}(p,s_{i})$
$\displaystyle\leq\text{dist}(p,\mathcal{S})+(\text{dist}(p,\mathcal{A})+\text{dist}(p,\mathcal{S}))\sum_{j=1}^{i}\left(\frac{\varepsilon^{2}}{8z^{2}}\right)^{i}$
$\displaystyle\leq\text{dist}(p,\mathcal{S})+\frac{\varepsilon^{2}}{4z^{2}}(\text{dist}(p,\mathcal{A})+\text{dist}(p,\mathcal{S}))$
$\displaystyle\leq\frac{8z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})+\frac{\varepsilon^{2}}{4z^{2}}\cdot(1+\frac{8z}{\varepsilon})\text{dist}(p,\mathcal{A})$
$\displaystyle\leq\frac{10z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A}),$

as promised in order to remove centers.

Last, we show that the first bullet of the lemma holds. We consider now the
standard assignment: $p$ is assigned to its closest center of
$\mathcal{S}^{\prime}$, instead of $s_{j}$. First, since we only removed
centers, it holds that
$\text{cost}(p,\mathcal{S})\leq\text{cost}(p,\mathcal{S}^{\prime})$. Second,
using Lemma 1, we have for any $\varepsilon^{\prime}=\frac{\varepsilon}{z\log
z/\varepsilon}$:

$\displaystyle\text{cost}(p,\mathcal{S}^{\prime})$
$\displaystyle\leq\text{cost}(p,s_{j})$
$\displaystyle\leq(1+\varepsilon^{\prime})\text{cost}(p,\mathcal{S})+\left(\frac{4z}{\varepsilon^{\prime}}\right)^{z-1}\cdot\left(\frac{\varepsilon^{2}}{4z^{2}}\right)^{z}\cdot(\text{dist}(p,\mathcal{A})+\text{dist}(p,\mathcal{S}))^{z}$
$\displaystyle\leq(1+\varepsilon^{\prime})\text{cost}(p,\mathcal{S})+\left(\frac{\varepsilon}{z}\right)^{z}\cdot(2\log
z/\varepsilon)^{z-1}\cdot(\text{cost}(p,\mathcal{A})+\text{cost}(p,\mathcal{S}))$
$\displaystyle\leq(1+\varepsilon^{\prime})\text{cost}(p,\mathcal{S})+\varepsilon^{\prime}(\text{cost}(p,\mathcal{A})+\text{cost}(p,\mathcal{S}))$

Hence, we conclude that

$\left|\text{cost}(p,\mathcal{S}^{\prime})-\text{cost}(p,\mathcal{S})\right|\leq\frac{\varepsilon}{z\log
z/\varepsilon}\left(\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{A})\right),$

which concludes the lemma. ∎

###  8.2 In Metrics with Bounded Doubling Dimension

We start by defining the Doubling Dimension of a metric space, and stating a
key lemma.

Consider a metric space $(X,\text{dist})$. For a point $p\in X$ and an integer
$r\geq 0$, we let $\beta(p,r)=\\{x\in X\mid\text{dist}(p,x)\leq r\\}$ be the
_ball_ around $p$ with radius $r$.

######  Definition 5.

The _doubling dimension_ of a metric is the smallest integer $d$ such that any
ball of radius $2r$ can be covered by $2^{d}$ balls of radius $r$.

Notably, the Euclidean space $\mathbb{R}^{d}$ has doubling dimension
$\theta(d)$.

A $\gamma$-_net_ of $V$ is a set of points $X\subseteq V$ such that for all
$v\in V$ there is an $x\in X$ such that $\text{dist}(v,x)\leq\gamma$, and for
all $x,y\in X$ we have $\text{dist}(x,y)>\gamma$. A net is therefore a set of
points not too close to each other, such that every point of the metric is
close to a net point. The following lemma bounds the cardinality of a net in
doubling metrics.

######  Lemma 19 (from Gupta et. al [GKL03]).

Let $(V,\text{dist})$ be a metric space with doubling dimension $d$ and,
diameter $D$, and let $X$ be a $\gamma$-net of $V$. Then $|X|\leq
2^{d\cdot\lceil\log_{2}(D/\gamma)\rceil}$.

The goal of this section is to prove the following lemma. Combined with
Theorem 1, it ensures the existence of small coreset in graphs with small
doubling dimension.

######  Lemma 20.

Let $M=(X,\text{dist})$ be a metric space with doubling dimension $d$, let
$P\subset X$, let $k$ and $z$ be positive integers and let $\varepsilon>0$.
Further, let $\mathcal{A}$ be a $c_{\mathcal{A}}$-approximate solution with at
most $k$ centers. There exists an $\mathcal{A}$-approximate centroid set for
$P$ of size

$|P|\cdot\left(\frac{z}{\varepsilon}\right)^{O(d)}$

A direct corollary of that lemma is the existence of a coreset in Doubling
Metrics, as it is enough to show the mere existence of a small centroid set
for applying Corollary 2.

######  Corollary 4.

Let $M=(X,\text{dist})$ be a metric space with doubling dimension $d$, and two
positive integers $k$ and $z$.

There exists an algorithm with running time $\tilde{O}(nk)$ that constructs an
$\varepsilon$-coreset for $(k,z)$-clustering on $P\subseteq X$ with size

$O\left(\frac{\log^{5}1/\varepsilon}{2^{O(z\log
z)}\min(\varepsilon^{2},\varepsilon^{z})}\left(kd+\log 1/\pi\right)\right)$

###### Proof.

We first compute a coreset of size $\tilde{O}(k^{3}d\varepsilon^{-2})$
[HJLW18]. Then, combining Theorem 1 and Lemma 20 yields an algorithm
constructing a coreset of size

$O\left(\frac{\log^{4}1/\varepsilon}{2^{O(z\log
z)}\min(\varepsilon^{2},\varepsilon^{z})}\left(kd\log 1/\varepsilon+k\log
kd/\varepsilon+\log 1/\pi\right)\right).$

If $\log k>d$ then $O(\log kd)=O(\log k)$. If $d>\log k$ then $O(kd+k\log
kd)=O(kd)$, hence the claimed bound follows. ∎

###### Proof of Lemma 20.

For each point $p\in P$, let $c$ be the center to which $p$ was assigned in
$\mathcal{A}$. Let
$B\left(p,\left(\frac{8z}{\varepsilon}\right)\text{dist}(p,c)\right)$ be the
metric ball centered around $p$ with radius
$\left(\frac{8z}{\varepsilon}\right)\cdot\text{dist}(p,c)$, and let $N_{p}$ be
an $\left(\frac{\varepsilon}{4z}\right)\cdot\text{dist}(p,\mathcal{A})$-net of
that ball.

Due to Lemma 19, $N_{p}$ has size $(\varepsilon/z)^{-O(d)}$. Additionally, let
$s_{f}$ be a point not in any
$B(p,\left(\frac{10z}{\varepsilon}\right)\text{dist}(p,\mathcal{A}))$, if such
a point exist.

Let $\mathcal{N}:=s_{f}\bigcup_{p\in Y}N_{p}$. We claim that $\mathcal{N}$ is
the desired approximate centroid set.

For a candidate solution $\mathcal{S}$, apply first Lemma 18, so that we can
assume that for any center $s\in\mathcal{S}$, and
$q=\text{argmin}_{p:\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})}\text{dist}(p,\mathcal{A})+\text{dist}(p,s)$,
there is no problematic point with respect to $q$ and $s$.

let $\tilde{\mathcal{S}}$ be the solution obtained by replacing every center
$s\in\mathcal{S}$ by $\tilde{s}\in\mathbb{C}$ as follows: let
$q=\text{argmin}_{p:\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})}\text{dist}(p,\mathcal{A})+\text{dist}(p,s)$.
Pick $\tilde{s}$ to be the closest point to $s$ in $N_{q}$. If such a $q$ does
not exist, pick $\tilde{s}=s_{f}$.

Now, let $p$ be a point such that
$\text{cost}(p,\mathcal{S})\leq\left(\frac{8z}{\varepsilon}\right)^{z}\cdot\text{cost}(p,\mathcal{A})$,
let $s$ be any center in $\mathcal{S}$ and $q$ defined as previously. Then, by
construction of the $\tilde{\mathcal{S}}$, there is a center $\tilde{s}$ with
$\text{dist}(s,\tilde{s})\leq\left(\frac{\varepsilon}{4z}\right)\text{dist}(q,\mathcal{A})$
and therefore, using that $p$ is no problematic:

$\displaystyle\text{cost}(p,\tilde{\mathcal{S}})$
$\displaystyle\leq\text{cost}(p,\tilde{s})\leq(1+\varepsilon)\text{cost}(p,s)+(1+z/\varepsilon)^{z-1}\text{cost}(s,\tilde{s})$
$\displaystyle\leq(1+\varepsilon)\text{cost}(p,\mathcal{S})+(2z/\varepsilon)^{z-1}\left(\frac{\varepsilon}{2z}\right)^{z}\text{cost}(q,\mathcal{A})$
$\displaystyle\leq(1+\varepsilon)\text{cost}(p,\mathcal{S})+\varepsilon\text{cost}(q,\mathcal{A})$
(28)
$\displaystyle\leq(1+\varepsilon)\text{cost}(p,\mathcal{S})+\varepsilon\text{cost}(p,\mathcal{A}).$
(29)

To show the other direction, for any point in $\tilde{\mathcal{S}}$ there is a
center $s$ with
$\text{dist}(s,\tilde{s})\leq\left(\frac{\varepsilon}{4z}\right)\text{dist}(q,\mathcal{A})$.
Hence the previous equations apply as well, and we can conclude: for a point
$p$ such that
$\text{cost}(p,\mathcal{S})\leq\left(\frac{8z}{\varepsilon}\right)^{z}\cdot\text{cost}(p,\mathcal{A})$,

$|\text{cost}(p,\mathcal{S})-\text{cost}(p,\tilde{\mathcal{S}})|\leq\varepsilon(\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{A})).$

Rescaling $\varepsilon$ concludes the lemma: there is an
$\mathcal{A}$-approximate centroid set with size $|P|\left(\frac{z^{2}\log
z/\varepsilon}{\varepsilon}\right)^{O(d)}=|P|\left(\frac{z}{\varepsilon}\right)^{O(d)}$.

∎

##  9 Graphs with Bounded Treewidth

In this section, we show that for graphs with treewidth $t$, there exists a
small approximate centroid set. Hence, the main framework provides an
algorithm computing a small coreset. We first define the treewidth of a graph:

######  Definition 6.

A tree decomposition of a graph $G=(V,E)$ is a tree $\mathcal{T}$ where each
node $b$ (call a bag) is a subset of $V$ and the following conditions hold:

  * •

The union of bags is $V$,

  * •

$\forall v\in V$, the nodes containing $v$ in $\mathcal{T}$ form a connected
subtree of $\mathcal{T}$, and

  * •

for all edge $(u,v)\in E$, there is one bag containing $u$ and $v$.

The treewidth of a graph $G$ is the smallest integer $t$ such that their
exists a tree decomposition with maximum size bag $t+1$.

######  Lemma 21.

Let $G=(V,E)$ be a graph with treewidth $t$, $X\subseteq V$ and $k,z>0$.
Furthermore, let $\mathcal{A}$ be solution to $(k,z)$-clustering for $X$.
Then, there exists an $\mathcal{A}$-approximate centroid set for
$(k,z)$-clustering on $V$ of size $\text{poly}(|X|)\left(\frac{z^{2}\log
z/\varepsilon}{\varepsilon}\right)^{O(t)}$.

Applying this lemma with $X$ yields the direct corollary:

######  Corollary 5.

Let $G=(V,E)$ be a graph with treewidth $t$, $X\subseteq V$, $k$ and $z>0$.

There exists an algorithm running time $\tilde{O}(nk)$ that constructs an
$\varepsilon$-coreset for $(k,z)$-clustering on $X$, with size

$O\left(\frac{\log^{5}1/\varepsilon}{2^{O(z\log
z)}\min(\varepsilon^{2},\varepsilon^{z})}\left(k\log
k+kt+\log(1/\pi)\right)\right).$

###### Proof.

Let $X\subseteq V$. We start by computing a $(k,\varepsilon)$-coreset $X_{1}$
of size $O(\text{poly}(k,1/\varepsilon,t))$, using the algorithm from [BBH+20]

We now apply our framework to $X_{1}$. Computing an approximation on $X_{1}$
takes time $\tilde{O}(|X_{1}|k)$, using the algorithm from Mettu and Plaxton
[MP04].

Lemma 21 ensure the existence of an approximate centroid set for $X_{1}$ with
size $\text{poly}(|X_{1}|)\left(\frac{z}{\varepsilon}\right)^{O(t)}$. Hence,
Corollary 2 and the framework developed in the previous sections gives an
algorithm that computes an $\varepsilon$-coreset of $X$ with size

$O\left(\frac{\log^{4}{1/\varepsilon}}{2^{O(z\log
z)}\min(\varepsilon^{2},\varepsilon^{z})}\left(k\log|X_{1}|+kt\log
1/\varepsilon+\log(1/\pi)\right)\right).$

Using that $|X_{1}|=O(\text{poly}(k,\varepsilon,t))$ yields a coreset of size

$O\left(\frac{\log^{5}1/\varepsilon}{2^{O(z\log
z)}\min(\varepsilon^{2},\varepsilon^{z})}\left(k\log
k+kt+\log(1/\pi)\right)\right).$

Instead of using [BBH+20], one could apply our algorithm repeatedly as in
Theorem 3.1 of [BJKW21], to reduce iteratively the number of distinct point
consider and to eventually get the same coreset size. The number of repetition
needed to achieve that size bound is $O(\log^{*}n)$, where $\log^{*}(x)$ is
the number of times $\log$ is applied to $x$ before the result is at most $1$;
formally $\log^{*}(x)=0$ for $x\leq 1$, and $\log^{*}(x)=1+\log^{*}\log x$ for
$x>1$. The complexity of this repetition is therefore $\tilde{O}(nk)$, and the
success probability $1-\pi$, as proven in [BJKW21]. ∎

For the proof of Lemma 21, we rely on the following structural lemma:777In the
statement of [BBH+20], the third item is slightly different. To recover our
statement from theirs, take $P_{A}=A$ when $|A|=O(t)$..

######  Lemma 22 (Lemma 3.7 of [BBH+20]).

Given a graph $G=(V,E)$ of treewidth $t$, and $X\subseteq V$, there exists a
collection $\mathcal{T}$ of subsets of $V$ such that:

  1. 1.

$\cup_{A\in\mathcal{T}}A=V$,

  2. 2.

$|\mathcal{T}|=\text{poly}(|X|)$,

  3. 3.

For each $A\in\mathcal{T}$, $|A\cap X|=O(t)$, and there exists $P_{A}\subseteq
V$ with $|P_{A}|=O(t)$ such that there is no edge between $A\setminus P_{A}$
and $V\setminus(A\cup P_{A})$.

Our construction relies on the following simple observation. Let $s$ be a
possible center, and $p$ be a vertex such that
$\text{cost}(p,s)\leq\left(\frac{4z}{\varepsilon}\right)^{z}\text{cost}(p,\mathcal{A})$.
Let $A\in\mathcal{T}$ such that $p\in A$. Then, either $s\in A$, or the path
connecting $p$ to $s$ has to go through $P_{A}$.

We use this observation as follows: it would be enough to replace a center $s$
from solution $\mathcal{S}$ by one that has approximately the same distance of
all points of $P_{A}$. The main question is : how should we round the
distances to $P_{A}$? The goal is to classify the potential centers into few
classes, such that taking one representative per class gives an approximate
centroid set. The previous observation indicates that classifying the centers
according to their distances to points of $P_{A}$ is enough. However, there
are too many different classes: instead, we round those distances.

Ideally, this rounding would ensure that for any point $p$ and any center $s$,
all centers in $s$’s class have same distance to $p$, up to an additive error
$\varepsilon(\text{cost}(p,s)+\text{cost}(p,\mathcal{A}))$. This would mean
rounding the distance from $s$ to any point in $P_{A}$ by that amount – for
instance, rounding to the closest multiple of
$\varepsilon(\text{cost}(p,s)+\text{cost}(p,\mathcal{A}))$. Nonetheless, this
way of rounding depends on each point $p$: a rounding according to $p$ may not
be suited for another point $q$. To cope with that, we will quite naturally
round distances according to the point $p$ that minimizes
$\text{cost}(p,s)+\text{cost}(p,\mathcal{A})$. Additionally, to ensure that
the number of classes stays bounded, it is not enough to round to the closest
multiple of $\varepsilon(\text{cost}(p,s)+\text{cost}(p,\mathcal{A}))$: we
also show that distances bigger than
$\frac{1}{\varepsilon}(\text{cost}(p,s)+\text{cost}(p,\mathcal{A}))$ can be
trimmed down to
$\frac{1}{\varepsilon}(\text{cost}(p,s)+\text{cost}(p,\mathcal{A}))$. That
way, for each point of $P_{A}$ there are only $1/\varepsilon^{2}$ many
possible rounded distances.

Hence, a class is defined by a certain point $p$, a part $A$ and by
$|P_{A}|=t$ many rounded distances: in total, that makes
$\text{poly}(|X|)\varepsilon^{-O(t)}$ many classes. The approximate centroid
set contains one representative of each class: this would prove Lemma 21. We
now make the argument formal, in particular to show that the error incurred by
the trimming is affordable.

###### Proof of Lemma 21.

Given a point $s\in V$ and a set $A\in\mathcal{T}$, we call a distance tuple
to $A$ $\mathbf{d}_{A}(s):=\left(\text{dist}(s,x)~{}|~{}\forall x\in X\cap
A\right)+\left(\text{dist}(s,x)~{}|~{}\forall x\in P_{A}\right)$. Let $q\in
X$: the rounded distance tuple of $s$ with respect to $q$ is
$\widetilde{\mathbf{d}_{A,q}}(s)$ defined as follows:

  1. 1.

For $x\in X\cap A$ or $x=q$, $\widetilde{d}(s,x)$ is the multiple of
$\frac{\varepsilon}{z}\cdot\text{dist}(x,\mathcal{A})$ smaller than
$\frac{10z}{\varepsilon}\text{dist}(x,\mathcal{A})$ closest to
$\text{dist}(s,x)$.

  2. 2.

For $y\in P_{A}$, $\widetilde{d}(s,y)$ is the multiple of
$\frac{\varepsilon^{3}}{8z^{3}}\cdot\text{dist}(q,\mathcal{A})$ smaller than
$\frac{200z^{3}}{\varepsilon^{3}}\text{dist}(q,\mathcal{A})$ closest to
$\text{dist}(s,y)$.

Now, for every $A\in\mathcal{T}$, $q\in X$ and every rounded distance tuple
$T$ to $A$ with respect to $q$ such that $\exists
s:T=\widetilde{\mathbf{d}_{A}}(s)$, $\mathbb{C}$ contains one point $s\in A$
having that rounded distance tuple.

##### Bounding the size of $\mathbb{C}$.

Fix some $A\in\mathcal{T}$, and $q\in X$. A rounded distance tuple to $A$ is
made of $O(t)$ many distances. Each of them takes its value among
$\text{poly}(z/\varepsilon)$ possible numbers, due to the rounding. Hence,
there are at most $\left(\frac{z}{\varepsilon}\right)^{O(t)}$ possible rounded
distance tuple to $A$, and so at most that many points in $\mathbb{C}$. Since
there are $\text{poly}(|X|)$ different choices for $A$ and $q$, the total size
of $\mathbb{C}$ is
$\text{poly}(|X|)\left(\frac{z}{\varepsilon}\right)^{O(t)}$.

##### Bounding the error.

We now bound the error induced by approximating a solution $\mathcal{S}$ by a
solution $\tilde{\mathcal{S}}\subseteq\mathbb{C}$.

First, by applying Lemma 18, we can assume that for any center
$s\in\mathcal{S}$, and
$q=\text{argmin}_{p:\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})}\text{dist}(p,\mathcal{A})+\text{dist}(p,s)$,
there is no problematic point with respect to $q$ and $s$.

Let $A\in\mathcal{T}$ such that $s\in A$, and
$q=\text{argmin}_{\begin{subarray}{c}p:\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})\end{subarray}}\text{dist}(p,\mathcal{A})+\text{dist}(p,s)$.
$\tilde{s}$ is chosen to have the same rounded distance tuple to $A$ with
respect to $q$ as $s$. $\tilde{\mathcal{S}}$ is the solution made of all such
$\tilde{s}$, for $s\in\mathcal{S}$.

As in the proof of Lemma 20, we first show that points close to $s$ have cost
preserved in $\tilde{s}$. We will later show that points with large distance
to $s$ have also large distance to $\tilde{s}$, to ensure that their distance
to $\tilde{\mathcal{S}}$ does not decrease.

Let $p\in X$ be an input point. By Lemma 18, $p$ is not problematic with
respect to $s$ and $q$. Note that $s$ is not necessarily the closest center to
$p$. We aim at showing that
$|\text{cost}(p,s)-\text{cost}(p,\tilde{s})|\leq\varepsilon(\text{cost}(p,s)+\text{cost}(p,\mathcal{A}))$.

First, when $p\notin X\cap A$, we distinguish two subcases:

  * •

either
$\text{dist}(p,s)\leq\frac{200z^{3}}{\varepsilon^{3}}\text{dist}(q,\mathcal{A})$:
in that case, let $x\in p_{A}$ that is on the shortest path between $p$ and
$s$. We have
$\text{dist}(s,x)\leq\frac{200z^{3}}{\varepsilon^{3}}\text{dist}(q,\mathcal{A})$,
and so $s$ and $\tilde{s}$ have the same rounded distance to $x$. Hence,

$\displaystyle\text{dist}(p,\tilde{s})$
$\displaystyle\leq\text{dist}(p,x)+\text{dist}(x,\tilde{s})\leq\text{dist}(p,x)+\text{dist}(x,s)+\frac{\varepsilon^{3}}{8z^{3}}\text{dist}(q,\mathcal{A})$
$\displaystyle\leq\text{dist}(p,s)+\frac{\varepsilon^{3}}{8z^{3}}\cdot\left(\frac{8z^{2}}{\varepsilon^{2}}\right)(\text{dist}(p,\mathcal{A})+\text{dist}(p,s))$
$\displaystyle\leq\left(1+\frac{\varepsilon}{z}\right)\text{dist}(p,s)+\frac{\varepsilon}{z}\text{dist}(p,\mathcal{A}),$

The first line implies that
$\text{dist}(p,\tilde{s})\leq\frac{200z^{3}}{\varepsilon^{3}}\text{dist}(q,\mathcal{A})$
as well: we can therefore repeat the argument, choosing $x$ to be on the
shortest path between $p$ and $\tilde{s}$ instead, to show that
$\text{dist}(p,s)\leq\left(1+\frac{\varepsilon}{z}\right)\text{dist}(p,\tilde{s})+\frac{\varepsilon}{z}\text{dist}(p,\mathcal{A})$.
This implies, using Lemma 1, that
$|\text{cost}(p,\tilde{s})-\text{cost}(p,s)|\leq\frac{\varepsilon}{z}\cdot(\text{cost}(p,s)+\text{cost}(p,\mathcal{A}))$.

  * •

Otherwise,
$\text{dist}(p,s)>\frac{200z^{3}}{\varepsilon^{3}}\text{dist}(q,\mathcal{A})$.
In that case, we can argue that $\text{dist}(s,\tilde{s})$ is negligible
compared to $\text{dist}(p,s)$. Recall that
$\text{dist}(q,s)\leq\frac{10z}{\varepsilon}\text{dist}(q,\mathcal{A})$.

The rounding ensures that the distance to $q$ is preserved:
$\text{dist}(q,\tilde{s})\leq\text{dist}(q,s)+\frac{\varepsilon}{z}\text{dist}(q,\mathcal{A})$.
Hence, we get that

$\displaystyle\text{dist}(s,\tilde{s})$ $\displaystyle\leq
2\text{dist}(q,s)+\frac{\varepsilon}{z}\text{dist}(q,\mathcal{A})$
$\displaystyle\leq\left(\frac{100z^{2}}{\varepsilon^{2}}+\frac{\varepsilon}{z}\right)\cdot\text{dist}(q,\mathcal{A})$
$\displaystyle\leq\frac{200z^{2}}{\varepsilon^{2}}\cdot\frac{\varepsilon^{3}}{200z^{3}}\cdot\text{dist}(p,s)\leq\frac{\varepsilon}{z}\cdot\text{dist}(p,s).$

Finally, using Lemma 1, we conclude again that
$|\text{cost}(p,\tilde{s})-\text{cost}(p,s)|\leq\varepsilon\text{cost}(p,s)+\varepsilon\text{cost}(p,\mathcal{A})$.

Now, in the other case where $p\in X\cap A$, if
$\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})$, then
the choice of $\tilde{s}$ ensures that
$|\text{dist}(\tilde{s},p)-\text{dist}(s,p)|\leq\frac{\varepsilon}{z}\text{dist}(x,\mathcal{A})$
and therefore
$|\text{cost}(p,s)-\text{cost}(p,\tilde{s})|\leq\varepsilon\text{cost}(p,s)+(1+z/\varepsilon)^{z-1}\text{cost}(s,\tilde{s})\leq\varepsilon\text{cost}(p,\mathcal{S})+\varepsilon\text{cost}(p,\mathcal{A})$.
In the last case when
$\text{dist}(p,s)>\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})$, then the
rounding enforces
$\text{dist}(p,\tilde{s})=\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})$.

Hence, in all possible cases, it holds that either $\text{dist}(p,s)$ and
$\text{dist}(p,\tilde{s})$ are bigger than
$\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})$, or:

$|\text{cost}(p,\tilde{s})-\text{cost}(p,s)|\leq\varepsilon\text{cost}(p,s)+\varepsilon\text{cost}(p,\mathcal{A}).$
(30)

To extend that result to the full solutions $\mathcal{S}$ and
$\tilde{\mathcal{S}}$ instead of a particular center, we note that since $p$
is interesting,
$\text{dist}(p,\mathcal{S})\leq\frac{8z}{\varepsilon}\text{dist}(p,\mathcal{A})$.
Hence, we can apply Eq. 30 with $s$ being the closest point to $p$ in
$\mathcal{S}$:
$\text{cost}(p,\tilde{\mathcal{S}})\leq(1+\varepsilon)\text{cost}(p,\mathcal{S})+\varepsilon\text{cost}(p,\mathcal{A})$.

In particular, this implies that
$\text{dist}(p,\tilde{s})\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})$.
Choose now $\tilde{s}$ to be the closest point to $p$ in $\tilde{\mathcal{S}}$
and $s$ its corresponding center in $\mathcal{S}$. Using Eq. 30 therefore
gives:

$\displaystyle\text{cost}(p,s)$
$\displaystyle\leq\text{cost}(p,\tilde{\mathcal{S}})+\varepsilon(\text{cost}(p,\mathcal{A})+\text{cost}(p,s))$
$\displaystyle\implies\text{cost}(p,s)$
$\displaystyle\leq\frac{1}{1-\varepsilon}\text{cost}(p,\tilde{\mathcal{S}})+\frac{\varepsilon}{1-\varepsilon}\text{cost}(p,\mathcal{A})$
$\displaystyle\leq(1+2\varepsilon)\text{cost}(p,\tilde{\mathcal{S}})+2\varepsilon\text{cost}(p,\mathcal{A})$
$\displaystyle\implies\text{cost}(p,\mathcal{S})$
$\displaystyle\leq(1+2\varepsilon)\text{cost}(p,\tilde{\mathcal{S}})+3\varepsilon\text{cost}(p,\mathcal{A}).$

Hence, combining those two inequalities yields

$|\text{cost}(p,\mathcal{S})-\text{cost}(p,\tilde{\mathcal{S}})|\leq\varepsilon\text{cost}(p,\mathcal{S})+2\varepsilon\text{cost}(p,\tilde{\mathcal{S}})+4\varepsilon\text{cost}(p,\mathcal{A}).$

To remove the dependency in $\text{cost}(p,\tilde{\mathcal{S}})$ from the
right hand side, one can upper bound it with
$\text{cost}(p,\mathcal{S})+|\text{cost}(p,\mathcal{S})-\text{cost}(p,\tilde{\mathcal{S}})|$,
which yields the following:

$\displaystyle|\text{cost}(p,\mathcal{S})-\text{cost}(p,\tilde{\mathcal{S}})|$
$\displaystyle\leq\varepsilon\text{cost}(p,\mathcal{S})+2\varepsilon\left(\text{cost}(p,\mathcal{S})+|\text{cost}(p,\mathcal{S})-\text{cost}(p,\tilde{\mathcal{S}})|\right)$
$\displaystyle\qquad+4\varepsilon\text{cost}(p,\mathcal{A})$
$\displaystyle\iff|\text{cost}(p,\mathcal{S})-\text{cost}(p,\tilde{\mathcal{S}})|$
$\displaystyle\leq\frac{1}{1-2\varepsilon}\left(3\varepsilon\text{cost}(p,\mathcal{S})+4\varepsilon\text{cost}(p,\mathcal{A})\right)$
$\displaystyle\leq
9\varepsilon\text{cost}(p,\mathcal{S})+12\varepsilon\text{cost}(p,\mathcal{A})$

Finally, rescaling $\varepsilon$ concludes.

∎

##  10 Planar Graphs

The goal of this section is to prove the existence of small centroid sets for
planar graph, analogously to the treewidth case. This is the following lemma:

######  Lemma 23.

Let $G=(V,E)$ be an edge-weighted planar graph, a set $X\subseteq V$ and two
positive integers $k$ and $z$. Furthermore, let $\mathcal{A}$ be a solution of
$(k,z)$-clustering of $X$.

Then, there exists an $\mathcal{A}$-approximate centroid set for
$(k,z)$-clustering on $V$ of size
$\text{poly}(|X|)\cdot\exp\big{(}O(z^{3}\varepsilon^{-3}\log
z/\varepsilon)\big{)}$.

As for treewidth, this lemma implies the following corollary:

######  Corollary 6.

Let $G=(V,E)$ be an edge-weighted planar graph, a set $X\subseteq V$, and two
positive integers $k$ and $z$ .

There exists an algorithm with running time $\tilde{O}(nk)$ that constructs an
$\varepsilon$-coreset for $(k,z)$-clustering on $X$ with size

$O\left(\frac{\log^{5}1/\varepsilon}{2^{O(z\log
z)}\min(\varepsilon^{2},\varepsilon^{z})}\left(k\log^{2}k+\frac{k\log
k}{\varepsilon^{3}}+\log 1/\pi\right)\right)$

The big picture is the same as for treewidth. As in the treewidth case, planar
graph can be broken into $\text{poly}(X)$ pieces, each containing at most $2$
vertices of $X$. The main difference is in the nature of the separators: while
treewidth admit small vertex separators, the region in the planar
decomposition are bounded by a few number of shortest path instead. This makes
the previous argument void: we cannot round distances to all vertices in the
boundary of a region. We show how to bypass this, using the fact that
separators are shortest paths: it is enough to round distances to a well-
chosen subset of the paths, as we will argue in the proof.

Formally, the decomposition is as follows:

######  Lemma 24 (Lemma 4.5 of [BJKW21], see also [EKM14]).

For every edge-weighted planar graph $G=(V,E)$ and subset $X\subseteq V$,
there exists a collection of subsets of $V$ $\Pi:=\\{V_{i}\\}$ with
$|\Pi|=\text{poly}(|X|)$ and $\cup V_{i}=V$ such that, for every
$V_{i}\in\Pi$:

  * •

$|V_{i}\cap X|=O(1)$, and

  * •

there exists a collection of shortest paths $\mathcal{P}_{i}$ with
$|\mathcal{P}_{i}|=O(1)$ such removing the vertices of all paths of
$\mathcal{P}_{i}$ disconnects $V_{i}$ from $V\setminus V_{i}$.

As for treewidth, we proceed as follows: given the decomposition of Lemma 24,
for any center $s\in V_{i}$, we identify a point $q$ and round distances from
$s$ to $\mathcal{P}_{i}$ according to $\text{dist}(q,\mathcal{A})$.
$\mathbb{C}$ contains one point $\tilde{s}$ with the same rounded distances as
$s$, and we will argue that $\tilde{s}$ can replace $s$. As mentioned, we
cannot round distances to the whole shortest-paths $\mathcal{P}_{i}$. Instead,
we show that it is enough to round distances from $s$ to points on the
boundary of $V_{i}$ that are close to $q$: since the boundary consists of
shortest path, it is possible to discretize that set.

###### Proof of Lemma 23.

Let $\Pi=\\{V_{i}\\}$ be the decomposition given by Lemma 24. For any $V_{i}$
and any $q\in X$, we define a set of _landmarks_ $\mathcal{L}_{i,q}$ as
follows: for any $P\in\mathcal{P}_{i}$, let $\mathcal{L}_{i,q,P}$ be a
$\frac{\varepsilon}{z}\cdot\text{dist}(q,\mathcal{A})$-net of $P\cap
B\left(q,\frac{90z^{2}}{\varepsilon^{2}}\cdot\text{dist}(q,\mathcal{A})\right)$.
Note that since $P$ is a shortest path, the total length of $P\cap
B\left(q,\frac{90z^{2}}{\varepsilon^{2}}\cdot\text{dist}(q,\mathcal{A})\right)$
is at most $\frac{180z^{2}}{\varepsilon^{2}}\cdot\text{dist}(q,\mathcal{A})$,
and so the net has size at most $\frac{180z^{3}}{\varepsilon^{3}}$. We define
$\mathcal{L}_{i,q}=\left(V_{i}\cap
X\right)\cup_{P\in\mathcal{P}_{i}}\mathcal{L}_{i,q,P}$.

Rounding the distances to $\mathcal{L}_{i,q}$ We now describe how we round
distances to landmarks, and define $\mathbb{C}$ such that for each possible
distance tuple, $\mathbb{C}$ contains a point having that distance tuple.
Formally, given a point $s\in V_{i}$ and a point $q\in X$, the distance tuple
$\mathbf{d}_{q}(s)$ of $s$ is defined as
$\mathbf{d}_{q}(s)=(\text{dist}(s,x)~{}|~{}\forall~{}x\in X\cap
V_{i})+\left(\text{dist}(s,y)~{}|~{}\forall y\in\mathcal{L}_{i,q},\forall
i\right)$. The _rounded distance tuple_ $\tilde{\mathbf{d}}_{q}(s)$ of $s$ is
defined as follows :

  * •

For $x\in X\cap V_{i}$ or $x=q$, $\tilde{d}(s,x)$ is the multiple of
$\frac{\varepsilon}{z}\text{dist}(x,\mathcal{A})$ smaller than
$\frac{10z}{\varepsilon}\text{dist}(x,\mathcal{A})$ closest to
$\text{dist}(s,x)$.

  * •

For $y\in\mathcal{L}_{i,q}$, $\tilde{d}(s,y)$ is the multiple of
$\frac{\varepsilon}{z}\cdot\text{dist}(q,\mathcal{A})$ smaller than
$\frac{90z^{2}}{\varepsilon^{2}}\text{dist}(q,\mathcal{A})$ closest to
$\text{dist}(s,y)$.

The set $\mathbb{C}$ is constructed as follows: for every $V_{i}$ and every
$q$, for every rounded distance tuple $\\{\tilde{\mathbf{d}}_{q}(p)\\}$, add
to $\mathbb{C}$ a point that realizes this rounded distance tuple (if such a
point exists).

It remains to show both that $\mathbb{C}$ has size
$\text{poly}(|X|)\exp\big{(}O(z^{3}\varepsilon^{-3}\log
z/\varepsilon)\big{)}$, and that $\mathbb{C}$ contains good approximation of
each center of any given solution.

##### Size analysis.

For any given $V_{i}$ and $q$, there are
$\left(\frac{90z^{3}}{\varepsilon^{3}}\right)^{|\mathcal{L}_{i,q}|}$ possible
rounded distances. As explained previously,
$|\mathcal{L}_{i,q}|=O(z^{3}/\varepsilon^{3})$.

There are $|V|$ choices of $q$, and Lemma 24 ensures that there are
$\text{poly}(|X|)$ choices for $V_{i}$.

Hence, the total size of $\mathbb{C}$ is at most
$\text{poly}(|X|)\cdot\exp\big{(}O(z^{3}\varepsilon^{-3}\log
z/\varepsilon)\big{)}$.

##### Error analysis.

We now show that for all solution $\mathcal{S}$, every center can be
approximated by a point of $\mathbb{C}$. First, by applying Lemma 18, we can
assume that for any center $s\in\mathcal{S}$, and
$q=\text{argmin}_{p:\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})}\text{dist}(p,\mathcal{A})+\text{dist}(p,s)$,
there is no problematic point with respect to $q$ and $s$.

Let $S$ be some cluster of $\mathcal{S}$, with center $s$. As in Lemma 20 and
21, we aim at showing how to find $\tilde{s}\in\mathbb{C}$ such that, for
every $p\in X\cap S$ with
$\text{dist}(p,\mathcal{S})\leq\frac{10z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$,
we have $|\text{cost}(p,s)-\text{cost}(p,\tilde{s})|\leq
3\varepsilon\left(\text{cost}(p,s)+\text{cost}(p,\mathcal{A})\right)$.

For this, let $V_{i}$ be a part of $\Pi$ containing $s$, and $\mathcal{P}_{i}$
be the paths given by Lemma 24. We let $q:=\text{argmin}_{p\in
X:\text{dist}(p,s)\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})}\text{dist}(p,s)+\text{dist}(p,\mathcal{A})$.
We define $\tilde{s}$ to be the point of $\mathbb{C}$ that has the same
rounded distance tuple to $\mathcal{L}_{i,q}$ as $s$. Let
$\tilde{\mathcal{S}}$ be the solution constructed from $\mathcal{S}$ that way.
We show now that $\tilde{\mathcal{S}}$ has the required properties.

First, if $p\notin V_{i}$, then we show how to use that $s$ and $\tilde{s}$
have the same rounded distances to $\mathcal{L}_{i,q}$.

  * •

If
$\text{dist}(p,s)>\frac{21z^{2}}{\varepsilon^{2}}\cdot\text{dist}(q,\mathcal{A})$,
we argue that $d(s,\tilde{s})$ is negligible. The argument is exactly alike
the one from Lemma 21, we repeat it for completeness.

The rounding ensures that the distance to $q$ is preserved:
$\text{dist}(q,\tilde{s})\leq\text{dist}(q,s)+\frac{\varepsilon}{z}\text{dist}(q,\mathcal{A})$,
and therefore:

$\displaystyle\text{dist}(s,\tilde{s})$ $\displaystyle\leq
2\text{dist}(q,s)+\frac{\varepsilon}{z}\cdot\text{dist}(q,\mathcal{A})$
$\displaystyle\leq\left(\frac{20z}{\varepsilon}+\frac{\varepsilon}{z}\right)\cdot\text{dist}(q,\mathcal{A})$
$\displaystyle\leq\frac{21z}{\varepsilon}\cdot\frac{\varepsilon^{2}}{21z^{2}}\cdot\text{dist}(p,s)\leq\frac{\varepsilon}{z}\cdot\text{dist}(p,s).$

Hence, using the modified triangle inequality Lemma 1, we can conclude:
$|\text{cost}(p,\tilde{s})-\text{cost}(p,s)|\leq\varepsilon\text{cost}(p,s)+\varepsilon\text{cost}(p,\mathcal{A})$.

  * •

Otherwise,
$\text{dist}(p,s)\leq\frac{21z^{2}}{\varepsilon^{2}}\cdot\text{dist}(q,\mathcal{A})$
and we can make use of the landmarks. Since $p\notin V_{i}$ the shortest-path
$p\leadsto s$ and crosses $\mathcal{P}_{i}$ at some vertex $x$.

First, it holds that
$\text{dist}(x,q)\leq\text{dist}(x,s)+\text{dist}(s,q)\leq\text{dist}(p,s)+\text{dist}(s,q)\leq(\frac{10z}{\varepsilon}+\frac{8z^{2}}{\varepsilon^{2}})\text{dist}(q,\mathcal{A})$,
hence $x$ is in $P\cap
B(q,\frac{90z^{2}}{\varepsilon^{2}}\text{dist}(q,\mathcal{A}))$. By choice of
landmarks, this implies that there is $\ell\in\mathcal{L}_{i,q}$, with
$\text{dist}(x,\ell)\leq\frac{\epsilon}{z}\text{dist}(q,\mathcal{A})$. To show
that $s$ and $\tilde{s}$ have the same distance to $\ell$, it is necessary to
show that $s$ is not too far away from $\ell$:

$\displaystyle\text{dist}(s,\ell)$
$\displaystyle\leq\text{dist}(s,x)+\frac{\epsilon}{z}\cdot\text{dist}(q,\mathcal{A})\leq\text{dist}(p,s)+\frac{\epsilon}{z}\text{dist}(q,\mathcal{A})$
$\displaystyle\leq\frac{21z^{2}}{\varepsilon^{2}}\cdot\text{dist}(q,\mathcal{A})+\frac{\varepsilon}{z}\cdot\text{dist}(q,\mathcal{A})$

Hence, $s$ is close enough to $\ell$ to ensure that $\tilde{s}$ has the same
rounded distance to $\ell$ as $s$, and we get:

$\displaystyle\text{dist}(p,\tilde{s})$
$\displaystyle\leq\text{dist}(p,\ell)+\text{dist}(\ell,\tilde{s})$
$\displaystyle\leq\text{dist}(p,\ell)+\text{dist}(\ell,s)+\frac{\epsilon}{z}\cdot\text{dist}(q,\mathcal{A})$
$\displaystyle\leq\text{dist}(p,x)+\text{dist}(x,s)+2\text{dist}(x,\ell)+\frac{\epsilon}{z}\cdot\text{dist}(q,\mathcal{A})$
$\displaystyle=\text{dist}(p,s)+\frac{3\epsilon}{z}\cdot\text{dist}(q,\mathcal{A})$

First, this ensures that
$\text{dist}(p,\tilde{s})\leq\frac{8z^{2}}{\varepsilon^{2}}\cdot\text{dist}(q,\mathcal{A})$,
and so we can repeat the argument switching roles of $s$ and $\tilde{s}$, to
get
$|\text{dist}(p,\tilde{s})-\text{dist}(p,s)|\leq\frac{3\epsilon}{z}\cdot\text{dist}(q,\mathcal{A})$
Using that $p$ is not problematic with respect to $q$ and $s$, we can conclude
that

$|\text{dist}(p,\tilde{s})-\text{dist}(p,s)|\leq\frac{3\epsilon}{z}\cdot(\text{dist}(p,\mathcal{A})+\text{dist}(p,s)).$

In turn, using Lemma 1, we conclude:

$|\text{cost}(p,\tilde{s})-\text{cost}(p,s)|\leq\varepsilon\cdot(\text{cost}(p,\mathcal{A})+\text{cost}(p,s)).$

Finally, in the case where $p\in V_{i}$, then we get either
$|\text{dist}(p,\tilde{s})-\text{dist}(p,s)|\leq\frac{\varepsilon}{z}\text{dist}(p,\mathcal{A})$
and we are done, or both $\text{dist}(p,\tilde{s})$ and $\text{dist}(p,s)$ are
bigger than $\frac{8z}{\varepsilon}\text{dist}(p,\mathcal{A})$.

We can now conclude, exactly as in the treewidth case: in all possible cases,
it holds that either $\text{dist}(p,s)$ and $\text{dist}(p,\tilde{s})$ are
bigger than $\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})$, or:

$|\text{cost}(p,\tilde{s})-\text{cost}(p,s)|\leq\varepsilon\text{cost}(p,s)+\varepsilon\text{cost}(p,\mathcal{A}).$
(31)

To extend that result to the full solutions $\mathcal{S}$ and
$\tilde{\mathcal{S}}$ instead of a particular center, we note that since $p$
is interesting,
$\text{dist}(p,\mathcal{S})\leq\frac{8z}{\varepsilon}\text{dist}(p,\mathcal{A})$.
Hence, we can apply Eq. 31 with $s$ being the closest point to $p$ in
$\mathcal{S}$:
$\text{cost}(p,\tilde{\mathcal{S}})\leq(1+\varepsilon)\text{cost}(p,\mathcal{S})+\varepsilon\text{cost}(p,\mathcal{A})$.

In particular, this implies that
$\text{dist}(p,\tilde{s})\leq\frac{10z}{\varepsilon}\text{dist}(p,\mathcal{A})$.
Chose now $\tilde{s}$ to be the closest point to $p$ in $\tilde{\mathcal{S}}$
and $s$ its corresponding center in $\mathcal{S}$. Using Eq. 31 therefore
gives:

$\displaystyle\text{cost}(p,\mathcal{S})$
$\displaystyle\leq(1+\varepsilon)\text{cost}(p,\tilde{\mathcal{S}})+\varepsilon\text{cost}(p,\mathcal{A})$
$\displaystyle\leq(1+\varepsilon)^{2}\text{cost}(p,\mathcal{S})+\varepsilon(2+\varepsilon)\text{cost}(p,\mathcal{A})$
$\displaystyle\leq(1+3\varepsilon)\text{cost}(p,\mathcal{S})+3\varepsilon\text{cost}(p,\mathcal{A}).$

Rescaling $\varepsilon$ and combining the two inequality concludes. ∎

##  11 Minor-Excluded Graphs

A graph $H$ is a minor of a graph $G$ if it can be obtained from $G$ by
deleting edges and vertices and contracting edges.

We are interested here in families of graph excluding a fixed minor $H$, i.e.
none of the graph in the family contains $H$ as a minor. The graphs are
weighted: we assume that for each edge, its value is equal to shortest-path
distance between its two endpoints.

The goal of this section is to prove the following lemma, analogous to Lemma
23.

######  Lemma 25.

Let $G=(V,E)$ be an edge-weighted graph that excludes a minor of fixed size, a
set $X\subseteq V$ and two positive integers $k$ and $z$. Furthermore, let
$\mathcal{A}$ be a solution of $(k,z)$-clustering of $X$.

Then, there exists an $\mathcal{A}$-approximate centroid set for
$(k,z)$-clustering on $V$ of size
$\exp(O(\log^{2}|X|+\log|X|/\varepsilon^{4}))$.

As for the bounded treewidth and planar cases, this lemma implies the
following corollary:

######  Corollary 7.

Let $G=(V,E)$ be an edge-weighted graph that excludes a fixed minor, and two
positive integers $k$ and $z$ .

There exists an algorithm with running time $\tilde{O}(nk)$ that constructs an
$\varepsilon$-coreset for $(k,z)$-clustering on $V$ with size

$O\left(\frac{\log^{5}1/\varepsilon}{2^{O(z\log
z)}\min(\varepsilon^{2},\varepsilon^{z})}\left(k\log^{2}k\log(1/\varepsilon)+\frac{k\log
k}{\varepsilon^{4}}+\log 1/\pi\right)\right)$

The big picture is the same as for planar graphs. Minor-free graphs have
somewhat nice separators, that we can use to select centers. However, those
separators are not shortest paths in the original graph, as described in the
next structural lemma.

######  Lemma 26 (Lemma 4.12 in [BJKW21], from Theorem 1 in [AG06]).

For every edge-weighted graph $G=(V,E)$ excluding some fixed minor, and subset
$X\subseteq V$, there exists a collection of subsets of $V$
$\Upsilon:=\\{\Pi_{i}\\}$ with $|\Upsilon|=\text{poly}(|X|)$ and
$\cup\Pi_{i}=V$ such that, for every $\Pi_{i}\in\Upsilon$:

  * •

$|\Pi_{i}\cap X|=O(1)$, and

  * •

there exists a groups of paths $\\{\mathcal{P}^{i}_{j}\\}$ with
$|\cup\mathcal{P}^{i}_{j}|=O(\log|X|)$ such that removing the vertices of all
paths of $\mathcal{P}_{i}$ disconnects $\Pi_{i}$ from $V\setminus\Pi_{i}$, and
such that paths in $\mathcal{P}^{i}_{j}$ are shortest-paths in the graph
$G^{i}_{j}:=G\setminus\left(\cup_{j^{\prime}<j}\mathcal{P}^{i}_{j^{\prime}}\right)$.

The general sketch of the proof is as follows: we consider the boundary $B$ of
a region $\Pi_{i}$, and enumerate all possible tuple of distances from a point
inside the leaf to the boundary. For each tuple, we include in $\mathbb{C}$ a
point realizing it. Of course, this would lead to a set $\mathbb{C}$ way too
big: the boundary of each leaf consists of too many points, and there are too
many distances possible. For that, we show how to discretize the boundary, and
how to round distances from a point to the boundary.

Discretizing the boundary is not as easy as in the planar case, as the
separating paths are not shortest paths in the original graph $G$. A
separating path $P\in\mathcal{P}_{j}$, however, is a shortest path in the
graph
$G^{i}_{j}:=G\setminus\left(\cup_{j^{\prime}<j}\mathcal{P}^{i}_{j^{\prime}}\right)$.

As in the planar case, we therefore start from the point $q$ closest to $s$ in
the graph $G^{i}_{j}$. Note here that we cannot infer much on the distances in
the original graph $G$: for this reason, we are not able to apply Lemma 18,
and we need to present a whole different argument.

We will assume that we know $D=\text{dist}_{j}(q,s)$, where $\text{dist}_{j}$
is the distance in the graph $G^{i}_{j}$. In that case, we can simply take an
$\varepsilon D$-net of $P\cap B_{j}(q,D)$, where $B_{j}(q,D)$ is the ball
centered at $q$ and of radius $D$ in $G^{i}_{j}$. This net has size
$O(1/\varepsilon^{2})$, as $P$ is a shortest path in $G^{i}_{j}$. Then, if
$\tilde{s}$ has same distances to this net as $s$, we are able to show as in
the previous cases that for any point separated from $s$ by $P$,
$\text{dist}(p,\tilde{s})\lessapprox\text{dist}(p,s)$; and for any point
separated from $\tilde{s}$ by $P$,
$\text{dist}(p,s)\lessapprox\text{dist}(p,\tilde{s})$.

To estimate $\text{dist}_{i}(q,s)$, we proceed as follows: either
$\text{dist}_{i}(q,s)\approx\text{dist}_{i}(q,q_{2})$ for some $q_{2}\in X$,
or not. In the first case, we can pick such a $q_{2}$. In the second case, we
will need to ensure that when $p$ is such that
$\text{dist}_{i}(p,q)\gg\text{dist}_{i}(q,s)$, then $\tilde{s}$ stays close to
$q$. When $p$ is such that $\text{dist}_{i}(q,p)\ll\text{dist}_{i}(q,s)$, then
$p$ and $q$ are essentially located at the same spot, and we ensure that
$\tilde{s}$ stays far from $q$.

###  11.1 Construction of the centroid set.

From Lemma 26, we have a decomposition into regions $\Upsilon=\\{\Pi_{i}\\}$.
In this argument, we fix a region $\Pi_{j}\in\Upsilon$. $\Pi_{j}$ is bounded
by $O(\log|X|)$ paths $P_{1},...,P_{m}$ and $P_{i}$ is a shortest path in some
graph $G_{i}$, subgraph of $G$: if $P_{i}\in\mathcal{P}^{j}_{\ell}$, then
$G_{i}:=G^{j}_{\ell}$. We change the indexing for simplicity, and let
$\Pi=\Pi_{j}$. We let $\text{dist}_{i}$ be the distances in the graph $G_{i}$.

We consider two ways of rounding the distances. The first starts from a point
$q_{1}\in X$, and is useful when there is $q_{2}\in X$ such that
$\varepsilon\text{dist}_{i}(q_{1},s)\leq\text{dist}_{i}(q_{1},q_{2})\leq\frac{1}{\varepsilon}\text{dist}_{i}(q_{1},s)$.

Along each paths, we designate portals as follows. Consider a path $P_{i}$.
For any pair of vertices $q_{1},q_{2}\in X$, let
$D=\text{dist}_{i}(q_{1},q_{2})+\text{dist}(q_{2},\mathcal{A})$ and let
$N_{i,q_{1},q_{2}}$ be an $\varepsilon^{2}D$-net of $P_{i}\cap
B_{i}(q_{1},\frac{D}{\varepsilon^{2}})$, where
$B_{i}(q,\frac{D}{\varepsilon^{2}})$ is the ball centered at $q$ and of radius
$\frac{D}{\varepsilon^{2}}$ in $G_{i}$.

For each possible $q_{1},q_{2}$ and any point $s\in\Pi$, we consider the
following distance tuple: $\left(\text{dist}_{i}(s,n),~{}\forall n\in
N_{i,q_{1},q_{2}}\right)\cup\left(\text{dist}_{i}(s,q_{1})\right)\cup\left(\text{dist}_{i}(x,s),~{}\forall
x\in\Pi\cap X\right)$. We define the rounded tuple
$\tilde{d}^{1}(q_{1},q_{2}):=\left(\tilde{d}^{1}(s,n),~{}\forall n\in
N_{i,q_{1},q_{2}}\right)\cup\left(\tilde{d}^{1}(s,q_{1})\right)\cup\left(\tilde{d}^{1}(x,s),~{}\forall
x\in\Pi\cap X\right)$, where

  * •

$\tilde{d}^{1}(s,n)$ is the multiple of $\varepsilon^{2}D$ closest to
$\min\left(\frac{3D}{\varepsilon^{2}},\text{dist}_{i}(s,n)\right)$.

  * •

$\tilde{d}^{1}(s,q_{1})$ is the multiple of $\varepsilon D$ closest to
$\text{dist}_{i}(s,q_{1})$ and smaller than $\frac{3D}{\varepsilon}$.

  * •

for any $x\in\Pi\cap X$, $\tilde{d}^{1}(x,s)$ is the closest multiple of
$\varepsilon\text{dist}(x,\mathcal{A})$ to $\text{dist}_{i}(x,s)$ smaller than
$\frac{1}{\varepsilon}\cdot\text{dist}(x,\mathcal{A})$.

We also consider another rounding, which will be helpful when for all points ,
$\text{dist}(p,\mathcal{A})+\text{dist}_{i}(q,q_{1})\notin[\varepsilon\text{dist}_{i}(q_{1},s),\frac{1}{\varepsilon}\text{dist}_{i}(q_{1},s)]$.

For any $q_{1},q_{3}$, and $q_{4}$ in $X$,
$\tilde{d}^{2}(q_{1},q_{3},q_{4})=\top$ when
$\frac{1}{\varepsilon}\cdot(\text{dist}_{i}(q_{1},q_{4})+\text{dist}(q_{4},\mathcal{A}))<\text{dist}_{i}(q_{1},s)<\varepsilon\cdot(\text{dist}_{i}(q_{1},q_{3})+\text{dist}(q_{3},\mathcal{A}))$,
and $\tilde{d}^{2}(q_{1},q_{3},q_{4})=\bot$ otherwise. $q_{3}$ or $q_{4}$ may
be unspecified. In that case, the corresponding part of the inequality is
dropped.888When $q_{3}$ is unspecified,
$\tilde{d}^{2}(q_{1},q_{3},q_{4})=\top$ when
$\frac{1}{\varepsilon}\cdot(\text{dist}_{i}(q_{1},q_{4})+\text{dist}(q_{4},\mathcal{A}))<\text{dist}_{i}(q_{1},s)$,
and $\tilde{d}^{2}(q_{1},q_{3},q_{4})=\bot$ otherwise. When $q_{4}$ is
unspecified, $\tilde{d}^{2}(q_{1},q_{3},q_{4})=\top$ when
$\text{dist}_{i}(q_{1},s)<\varepsilon\cdot(\text{dist}_{i}(q_{1},q_{3})+\text{dist}(q_{3},\mathcal{A}))$,
and $\tilde{d}^{2}(q_{1},q_{3},q_{4})=\bot$ otherwise.

To construct $\mathbb{C}$, we proceed as follows: for any region
$\Pi\in\Upsilon$ given by Lemma 26, and for any path $P_{i}$ in the boundary
of $\Pi$, select a rounding $\tilde{d}_{i}^{1}(q^{i}_{1},q^{i}_{2})$ or
$\tilde{d}_{i}^{2}(q^{i}_{1},q^{i}_{3},q^{i}_{4})$. If there is any, pick one
point $s$ achieving all those rounding distances, and add $s$ to $\mathbb{C}$.

We will show Lemma 25 using this centroid set. For that, we break the proof
into two parts: first, the size of $\mathbb{C}$ is the desired one; then,
$\mathbb{C}$ is indeed an approximate centroid set.

###  11.2 $\mathbb{C}$ has Small Size

######  Lemma 27.

$\mathbb{C}$ constructed as previously has size
$\exp\left(O(\log^{2}|X|+\log|X|/\varepsilon^{-4})\right)$.

###### Proof.

Fix a region $\Pi$, a path $P_{i}$ on $\Pi$’s boundary, and points
$q_{1},q_{2}$. There are $O\left(1/\varepsilon^{4}\right)$ points in the net
$N_{i,q_{1},q_{2}}$, and $O(1)$ in $\Pi\cap X$. For each of those points,
there are at most $3/\varepsilon^{4}$ many choices of distances.

For a fixed region $\Pi$, path $P_{i}$ on $\Pi$’s boundary, and points
$q_{1},q_{2},q_{3}$, there only $2$ possible different
$\tilde{d}^{2}(q_{1},q_{2},q_{3})$.

Now, there are $\text{poly}(|X|)$ many regions $\Pi$, and for each of them
$O(\log|X|)$ many paths $P_{i}$. For each path, there are at most $|X|^{3}$
choices of $q_{j}$ for it, so in total $|X|^{O(\log|X|)}$ possible choices.
Each choice gives rise to $O(\log|X|)\cdot O\left(1/\varepsilon^{4}\right)$
many net points, each having at most $3/\varepsilon^{4}$ many choices of
distances.

So, in total, there are

$|X|^{O(\log|X|)}\cdot(1/\varepsilon)^{O\left(\log|X|/\varepsilon^{4}\right)}$

many choices of rounded distances tuples. That upper bounds the size of
$\mathbb{C}$, as there is at most one point per rounded distance tuple. ∎

###  11.3 $\mathbb{C}$ is an Approximate Centroid Set

##### Construction of solution $\tilde{\mathcal{S}}$.

Now, for a point $s\in\mathcal{S}$, we construct $\tilde{s}$ as follows, using
the rounded distance tuples. Let $\Pi$ be a region of $\Upsilon$ that contains
$s$. For each path $P_{i}$ in the boundary of $\Pi$, we define the tuple
$\tilde{d}_{i}$ as follows. Let $q_{1}^{i}$ be the point minimizing
$\text{dist}_{i}(p,s)$. Now, we distinguish two cases:

  * •

either there is some $q^{i}_{2}$ such that
$\varepsilon\text{dist}_{i}(q^{i}_{1},s)\leq\text{dist}_{i}(q^{i}_{1},q^{i}_{2})+\text{dist}(q^{i}_{2},\mathcal{A})\leq\frac{1}{\varepsilon}\text{dist}_{i}(q^{i}_{1},s)$.
Then $\tilde{d}_{i}$ is the tuple $\tilde{d}^{1}(q^{i}_{1},q^{i}_{2})$.

  * •

or there exists points $q$ with
$\text{dist}_{i}(q^{i}_{1},q)+\text{dist}(q,\mathcal{A})>\frac{1}{\varepsilon}\text{dist}_{i}(q^{i}_{1},s)$:
let $q^{i}_{3}$ be such a point, with smallest
$\text{dist}_{i}(q^{i}_{1},q^{i}_{3})+\text{dist}(q^{i}_{3},\mathcal{A})$
value. If there are no such points, $q^{i}_{3}$ is unspecified.

If there are points $q$ with
$\text{dist}_{i}(q^{i}_{1},q)+\text{dist}(q,\mathcal{A})<\varepsilon\text{dist}_{i}(q^{i}_{1},s)$,
then let $q^{i}_{4}$ be the point with largest
$\text{dist}_{i}(q^{i}_{1},q^{i}_{4})+\text{dist}(q^{i}_{4},\mathcal{A})$
value. Otherwise, $q^{i}_{4}$ is unspecified. Note that since we are not in
the first case, either $q^{i}_{3}$ are $q^{i}_{4}$ is specified.

Then $\tilde{d}_{i}$ is the tuple
$\tilde{d}^{2}(q^{i}_{1},q^{i}_{3},q^{i}_{4})$.

$\tilde{s}$ is chosen to be in $\mathbb{C}\cap\Pi$ and to have the same
rounded distance tuples as $s$, for all the rounded tuples $\tilde{d}_{i}$.
$\tilde{\mathcal{S}}$ is the union of all those $\tilde{s}$ for
$s\in\mathcal{S}$.

######  Lemma 28.

Let $\mathcal{S}$ be a solution, and $s\in\mathcal{S}$. Let $\tilde{s}$
defined as previously. For any point $p\in X$, either
$|\text{cost}(p,s)-\text{cost}(p,\tilde{s})|\leq\varepsilon(\text{cost}(p,s)+\text{cost}(p,\mathcal{A}))$
or both $\text{dist}(p,s)$ and $\text{dist}(p,\tilde{s})$ are bigger than
$\frac{10z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$.

###### Proof.

Fix $s\in\mathcal{S}\cap\Pi$, and let $\tilde{s}$ be its corresponding point
in $\tilde{\mathcal{S}}$. Let $s_{1}\in\\{s,\tilde{s}\\}$, and $s_{2}$ the
other choice: we will show that
$\text{dist}(p,s_{1})\leq(1+\varepsilon)\text{dist}(p,s_{2})+\varepsilon\text{dist}(p,\mathcal{A})$.
This implies that the costs verify the same inequality, which will allow us to
conclude, switching the roles of $s_{1}$ and $s_{2}$.

First, in the case where $p\in\Pi\cap X$, then the rounding directly ensures
that either $\text{dist}(p,s)>1/\varepsilon\cdot\text{dist}(x,\mathcal{A})$,
in which case it holds as well than
$\text{dist}(p,\tilde{s})>1/\varepsilon\cdot\text{dist}(x,\mathcal{A})$, or
$|\text{dist}(p,s)-\text{dist}(p,\tilde{s})|\leq\varepsilon\text{dist}(x,\mathcal{A}))$.

Otherwise, $p$ is separated from $s_{1}$ by some path among
$\\{P_{1},...,P_{m}\\}$. Let $i$ be the smallest integer such that $P_{i}$
intersects the shortest path between $p$ and $s_{1}$. Our argument depends on
the type of tuple $\tilde{d}_{i}$ chosen for $s$. Since $s$ and $\tilde{s}$
have the same rounded distance tuples $\tilde{d}_{1},\tilde{d}_{2},...$, they
have in particular the same rounded distance $\tilde{d}_{i}$. Let $q^{i}_{1}$
be the point with smallest $\text{dist}_{i}(q,s)$ value (importantly, the
$q^{i}_{1},q^{i}_{2},q^{i}_{3}$ and $q^{i}_{4}$ appearing in the proof are
defined with respect to $s$, not to $s_{1}$).

##### If we can estimate $\text{dist}_{i}(q^{i}_{1},s)$.

In the first case, there is a $q^{i}_{2}$ such that
$\varepsilon\text{dist}_{i}(q^{i}_{1},s)\leq\text{dist}_{i}(q^{i}_{1},q^{i}_{2})+\text{dist}(q^{i}_{2},\mathcal{A})\leq\frac{1}{\varepsilon}\text{dist}_{i}(q^{i}_{1},s)$.
We let
$D:=\text{dist}_{i}(q^{i}_{1},q^{i}_{2})+\text{dist}(q^{i}_{2},\mathcal{A})$
our (rough) estimate on the distance $\text{dist}_{i}(q^{i}_{1},s)$.

Then, our argument goes as follows. Let $x$ be a point in the intersection of
$P_{i}$ and the shortest path $s_{1}\leadsto p$. We have the following
properties: by choice of $i$, $\text{dist}_{i}(p,s_{1})=\text{dist}(p,s_{1})$
and $\text{dist}_{i}(x,s_{1})=\text{dist}(x,s_{1})$. By choice of $x$,
$\text{dist}(p,x)+\text{dist}(x,s_{1})=\text{dist}(p,s_{1})$. Last, by choice
of $q^{i}_{1}$, $\text{dist}_{i}(q^{i}_{1},s)\leq\text{dist}_{i}(p,s)$, and
$D\leq\frac{\text{dist}_{i}(p,s)}{\varepsilon}$.

  * •

First, if $\text{dist}_{i}(x,q^{i}_{1})\leq\frac{D}{\varepsilon^{2}}$. Then
there is a point $n$ from $N_{i,q^{i}_{1},q^{i}_{2}}$ with
$\text{dist}_{i}(n,x)\leq\varepsilon^{2}D$. Furthermore,
$\text{dist}_{i}(s_{1},n)=\text{dist}_{i}(s_{2},n)\pm\varepsilon^{2}D$, as
$\text{dist}_{i}(s,n)\leq\text{dist}_{i}(s,x)+\text{dist}_{i}(x,q^{i}_{1})+\text{dist}_{i}(q^{i}_{1},s)\leq\frac{3D}{\varepsilon^{2}}$
and so $n$ has same rounded distances to $s_{1}$ and $s_{2}$. Hence, we get:

$\displaystyle\text{dist}_{i}(p,s_{2})$
$\displaystyle\leq\text{dist}_{i}(p,x)+\text{dist}_{i}(x,n)+\text{dist}_{i}(n,s_{2})$
$\displaystyle\leq\text{dist}_{i}(p,x)+\text{dist}_{i}(x,n)+\text{dist}_{i}(n,s_{1})+\varepsilon^{2}D$
$\displaystyle\leq\text{dist}_{i}(p,x)+\text{dist}_{i}(x,s_{1})+2\text{dist}_{i}(x,n)+\varepsilon^{2}D$
$\displaystyle\leq\text{dist}_{i}(p,s_{1})+3\varepsilon^{2}D$
$\displaystyle\leq\text{dist}(p,s_{1})+3\varepsilon\text{dist}_{i}(p,s).$

Now, two cases: either $s=s_{1}$ and $\text{dist}_{i}(p,s)=\text{dist}(p,s)$,
and then we get
$\text{dist}(p,s_{2})\leq(1+3\varepsilon)\text{dist}(p,s_{1})$. Or $s=s_{2}$,
and we have $(1-3\varepsilon)\text{dist}(p,s)\leq\text{dist}(p,\tilde{s})$
which implies $\text{dist}(p,s_{2})\leq(1+6\varepsilon)\text{dist}(p,s_{1})$.

  * •

Otherwise, $\text{dist}_{i}(x,q^{i}_{1})>\frac{D}{\varepsilon^{2}}$: we first
show that $\text{dist}(s,\tilde{s})\leq
3\varepsilon(\text{dist}_{i}(p,s)+\text{dist}(p,\mathcal{A}))$, which will
allow to conclude. It holds that
$\text{dist}_{i}(q^{i}_{1},s)=\text{dist}_{i}(q^{i}_{1},\tilde{s})\pm\varepsilon
D$, as by definition of $D$, $\text{dist}_{i}(q^{i}_{1},s)\leq D/\varepsilon$.
Hence,

$\displaystyle\text{dist}_{i}(s,\tilde{s})$
$\displaystyle\leq\text{dist}_{i}(s,q^{i}_{1})+\text{dist}_{i}(\tilde{s},q^{i}_{1})\leq
2\text{dist}_{i}(s,q^{i}_{1})+\varepsilon D$
$\displaystyle\leq\frac{2+\varepsilon^{2}}{\varepsilon}D\leq
3\varepsilon\text{dist}_{i}(x,q^{i}_{1})$ $\displaystyle\leq
3\varepsilon(\text{dist}_{i}(x,s_{1})+\text{dist}_{i}(s_{1},s_{2})+\text{dist}_{i}(s,q^{i}_{1}))$
$\displaystyle\Rightarrow\text{dist}(s,\tilde{s})$ $\displaystyle\leq
9\varepsilon(\text{dist}(p,s_{1})+\text{dist}_{i}(p,s)).$

Hence,

$\displaystyle\text{dist}_{i}(p,s_{2})$
$\displaystyle\leq\text{dist}_{i}(p,s_{1})+\text{dist}_{i}(s,\tilde{s})$
$\displaystyle\leq\text{dist}(p,s_{1})+9\varepsilon(\text{dist}(p,s_{1})+\text{dist}_{i}(p,s))$

Similarly as in the previous case, either $s_{1}=s$ and the right hand side is
$(1+18\varepsilon)\text{dist}(p,s_{1})$, or $s_{2}=s$ and we infer
$\text{dist}(p,s_{2})\leq(1+27\varepsilon)\text{dist}(p,s_{1})$.

##### When we can only overestimate or underestimate
$\text{dist}_{i}(q^{i}_{1},s)$

In the second case, $q^{i}_{3}$ is such that
$\text{dist}(q^{i}_{3},\mathcal{A})+\text{dist}_{i}(q^{i}_{1},q^{i}_{3})>\frac{1}{\varepsilon}\text{dist}_{i}(q^{i}_{1},s)$,
and has minimal
$\text{dist}_{i}(q^{i}_{1},q^{i}_{3})+\text{dist}(q^{i}_{3},\mathcal{A})$
value among those. Similarly, $q^{i}_{4}$ is the point with largest
$\text{dist}_{i}(q^{i}_{1},q^{i}_{4})+\text{dist}(q^{i}_{4},\mathcal{A})$
value among those verifying
$\text{dist}_{i}(q^{i}_{1},q)+\text{dist}(q,\mathcal{A})<\varepsilon\text{dist}_{i}(q^{i}_{1},s)$.

By choice of $q^{i}_{3}$ and $q^{i}_{4}$, it must be that

$\frac{1}{\varepsilon}\cdot(\text{dist}_{i}(q^{i}_{1},q^{i}_{4})+\text{dist}(q^{i}_{4},\mathcal{A}))<\text{dist}_{i}(q^{i}_{1},s)<\varepsilon\cdot(\text{dist}_{i}(q^{i}_{1},q^{i}_{3})+\text{dist}(q^{i}_{3},\mathcal{A})).$

Hence, $\tilde{d}^{2}(q^{i}_{1},q^{i}_{3},q^{i}_{4})=\top$, and $\tilde{s}$ is
chosen such that

$\frac{1}{\varepsilon}\cdot(\text{dist}_{i}(q^{i}_{1},q^{i}_{4})+\text{dist}(q^{i}_{4},\mathcal{A}))<\text{dist}_{i}(q^{i}_{1},\tilde{s})<\varepsilon\cdot(\text{dist}_{i}(q^{i}_{1},q^{i}_{3})+\text{dist}(q^{i}_{3},\mathcal{A})).$

Since we are not in the first case where we can estimate
$\text{dist}_{i}(q^{i}_{1},s)$, $p$ verifies either
$\text{dist}(p,\mathcal{A})+\text{dist}_{i}(p,q^{i}_{1})<\varepsilon\text{dist}_{i}(q_{1}^{i},s)$
or
$\text{dist}(p,\mathcal{A})+\text{dist}_{i}(p,q^{i}_{1})>\frac{1}{\varepsilon}\text{dist}_{i}(q_{1}^{i},s)$.

First, if
$\text{dist}_{i}(p,q^{i}_{1})+\text{dist}(p,\mathcal{A})>\frac{1}{\varepsilon}\text{dist}_{i}(q_{1}^{i},s)$.
Then we have, by choice of $q^{i}_{3}$:

$\displaystyle\text{dist}_{i}(s,\tilde{s})$
$\displaystyle\leq\text{dist}_{i}(s,q^{i}_{1})+\text{dist}_{i}(\tilde{s},q^{i}_{1})$
$\displaystyle\leq
2\varepsilon(\text{dist}_{i}(q^{i}_{1},q^{i}_{3})+\text{dist}(q^{i}_{3},\mathcal{A}))$
$\displaystyle\leq
2\varepsilon(\text{dist}_{i}(q^{i}_{1},p)+\text{dist}(p,\mathcal{A}))$
$\displaystyle\leq
2\varepsilon(\text{dist}_{i}(p,s)+\text{dist}_{i}(q^{i}_{1},s)+\text{dist}(p,\mathcal{A}))$
$\displaystyle\leq
4\varepsilon(\text{dist}_{i}(p,s)+\text{dist}(p,\mathcal{A}))$

and therefore, we can conclude just as before (distinguishing whether
$s=s_{1}$ or $s=s_{2}$) that

$\text{dist}(p,s_{2})\leq(1+12\varepsilon)\text{dist}(p,s_{1})+12\varepsilon\text{dist}(p,\mathcal{A}).$

Lastly, in the case where
$\text{dist}_{i}(p,q^{i}_{1})+\text{dist}(p,\mathcal{A})<\varepsilon\text{dist}_{i}(q_{1}^{i},s)$,
we use that
$\text{dist}_{i}(q^{i}_{1},s_{1})>\frac{1}{\varepsilon}\cdot(\text{dist}_{i}(q^{i}_{1},q^{i}_{4})+\text{dist}(q^{i}_{4},\mathcal{A}))$
(as both $s$ and $\tilde{s}$ verifies this) to get:

$\displaystyle\text{dist}(p,s_{1})$
$\displaystyle=\text{dist}_{i}(p,s_{1})\geq\text{dist}_{i}(q^{i}_{1},s_{1})-\text{dist}_{i}(p,q^{i}_{1})$
$\displaystyle\geq\frac{1}{\varepsilon}\cdot(\text{dist}_{i}(q^{i}_{1},q^{i}_{4})+\text{dist}(q^{i}_{4},\mathcal{A}))-\text{dist}_{i}(p,q^{i}_{1})$
$\displaystyle\geq\frac{1}{\varepsilon}\cdot(\text{dist}_{i}(q^{i}_{1},p)+\text{dist}(p,\mathcal{A}))-\text{dist}_{i}(p,q^{i}_{1})$
$\displaystyle\geq\frac{\text{dist}(p,\mathcal{A})}{\varepsilon}.$

##### Conclusion.

Rescaling $\varepsilon$ by $1/27z$, the previous inequalities gives us that
either
$\text{dist}(p,s_{1})\geq\frac{27z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$,
or
$\text{dist}(p,s_{2})\leq(1+\varepsilon/z)\text{dist}(p,s)+\varepsilon/z\cdot\text{dist}(p,\mathcal{A})$.
The second inequality combined with Lemma 1 implies that
$\text{cost}(p,s_{2})\leq(1+\varepsilon)\text{cost}(p,s_{1})+\varepsilon\cdot\text{cost}(p,\mathcal{A})$.
Therefore, using this result with $s_{1}=s,s_{2}=\tilde{s}$ and then
$s_{1}=\tilde{s},s_{2}=s$ shows that:

  * •

either
$\text{dist}(p,s)\geq\frac{27z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$,
or
$\text{cost}(p,\tilde{s})\leq(1+\varepsilon)\text{cost}(p,s)+\varepsilon\cdot\text{cost}(p,\mathcal{A})$

  * •

either
$\text{dist}(p,\tilde{s})\geq\frac{27z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$,
or
$\text{cost}(p,s)\leq(1+\varepsilon)\text{cost}(p,\tilde{s})+\varepsilon\cdot\text{cost}(p,\mathcal{A})$.

Therefore, if $p$ is such that
$\text{dist}(p,s)\leq\frac{5z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$,
then
$\text{dist}(p,\tilde{s})\leq\frac{10z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$,
and reciprocally when
$\text{dist}(p,\tilde{s})\leq\frac{5z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$,
then
$\text{dist}(p,s)\leq\frac{10z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$.

Thus we conclude: either both $\text{dist}(p,\tilde{s})$ and
$\text{dist}(p,s)$ are bigger than
$\frac{10z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$, and we are done. Or
both are smaller than
$\frac{20z\cdot\text{dist}(p,\mathcal{A})}{\varepsilon}$, and then using the
previous inequalities we get:

$|\text{cost}(p,s)-\text{cost}(p,\tilde{s})|\leq
2\varepsilon(\text{cost}(p,s)+\text{cost}(p,\tilde{s})+\text{cost}(p,\mathcal{A}))$

Which, using
$\text{cost}(p,\tilde{s})\leq\text{cost}(p,s)+|\text{cost}(p,s)-\text{cost}(p,\tilde{s})|$,
yields

$|\text{cost}(p,s)-\text{cost}(p,\tilde{s})|\leq
7\varepsilon(\text{cost}(p,s)+\text{cost}(p,\mathcal{A})).$

∎

Lemma 28 gives exactly the same guarantee as Eq. 30: hence, as in the proof
for treewidth, we can conclude from that inequality that for any solution
$\mathcal{S}$ and any interesting point $p$,
$|\text{cost}(p,\mathcal{S})-\text{cost}(p,\tilde{\mathcal{S}})|\leq\varepsilon(\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{A}))$.

Combining the guarantees from Lemma 28 and Lemma 27 concludes the proof of
Lemma 25.

##  12 A Note on Euclidean Spaces

Lastly, we briefly want to survey the state of the art results for eliminating
the dependency on the dimension in Euclidean spaces.

In a nutshell, the frameworks by both Feldman and Langberg [FL11] and us only
yield coresets of size $O(kd\text{poly}(\log k,\varepsilon^{-1}))$. To
eliminate the dependency on the dimension, we typically have to use some form
of dimension reduction.

In a landmark paper, [FSS20] showed that one can replace the dependency on $d$
with a dependency on $k/\varepsilon^{2}$ for the $k$-means problem, see also
[CEM+15] for further improvements on this idea. Subsequently, Sohler and
Woodruff [SW18] gave a construction for arbitrary $k$-clustering objectives
which lead to the first existence proof of dimension independent coresets for
these problems. Unfortunately, there were a few caveats; most notably a
running time exponential in both $k$. Huang and Vishnoi [HV20] showed that the
mere existence of the Sohler-Woodruff construction was enough to compute
coresets of size $\text{poly}(k/\varepsilon)$. Recently, the Sohler-Woodruff
result was made constructive in the work of Feng, Kacham and Woodruff [FKW19].

Having obtained a $\text{poly}(k/\varepsilon)$-sized coreset, one can now use
a terminal embedding to replace the dependency on $d$ by a dependency
$\varepsilon^{-2}\log k/\varepsilon$. Terminal embeddings are defined as
follows:

######  Definition 7 (Terminal Embeddings).

Let $\varepsilon\in(0,1)$ and let $A\subset\mathbb{R}^{d}$ be arbitrary with
$|A|$ having size $n>1$. Define the Euclidean norm of a $d$-dimensional vector
$\|x\|=\sqrt{\sum_{i=1}^{d}x_{i}^{2}}$. Then a mapping
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$ is a _terminal embedding_ if

$\forall x\in A,~{}\forall
y\in\mathbb{R}^{d},~{}(1-\varepsilon)\cdot\|x-y\|\leq\|f(x)-f(y)\|\leq(1+\varepsilon)\cdot\|x-y\|.$

Terminal embeddings were studied by [EFN17, MMMR18, NN19], with Narayanan and
Nelson [NN19] achieving an optimal target dimension of $O(\varepsilon^{-2}\log
n)$, where $n$ is the number of points999See the paper by Larsen and Nelson
for a matching lower bound [LN17].

It was first observed by Becchetti et al. [BBC+19] how terminal embeddings can
be combined with the Feldman-Langberg [FL11] (or indeed our) framework.
Specifically, given the existence of a $\text{poly}(k/\varepsilon)$-sized
coreset, applying a terminal embedding with $n$ being the number of distinct
points in the coreset now allows us to further reduce the dimension. At the
time, the only problem with such a coreset bound was $k$-means. The
generalization to arbitrary $k$-clustering objectives is now immediate
following the results by Huang and Vishnoi [HV20] and Feng et al. [FKW19].

It should be noted that more conventional Johnson-Lindenstrauss type
embeddings proposed in [BBC+19, CEM+15, MMR19] do not (obviously) imply the
same guarantee as terminal embeddings. We appended a short proof showing that
terminal embeddings are sufficient at the end of this section. For a more in-
depth discussion as to why normal Johnson-Lindenstrauss transforms may not be
sufficient, we refer to Huang and Vishnoi [HV20].

Combining our $O(k(d+\log k)\cdot\varepsilon^{-\max(2,z)})$ bound for general
Euclidean spaces with either the Huang and Vishnoi [HJV19] or the Feng et al.
[FKW19] constructions and terminal embeddings now immediately imply the
following corollary.

######  Corollary 8.

There exists a coreset of size

$O\left(k\log k\cdot\left(\varepsilon^{-2-\max(2,z)}\right)\cdot 2^{O(z\log
z)}\cdot\mathrm{polylog}(\varepsilon^{-1})\right)$

for $(k,z)$-clustering in Euclidean spaces.

Huang and Vishnoi further considered clustering in $\ell_{p}$ metrics for
$p\in[1,2)$, i.e. non-Euclidean spaces. For this they reduced constructing a
coreset for $(k,z)$ clustering in an $\ell_{p}$ space to constructing a
constructing a coreset for $(k,2z)$ clustering in Euclidean space. Plugging in
our framework into their reduction then yields the following corollary:

######  Corollary 9.

There exists a coreset of size

$O\left(k\log k\cdot\left(\varepsilon^{-2-2z}\right)\cdot 2^{O(z\log
z)}\cdot\mathrm{polylog}(\varepsilon^{-1})\right)$

for $(k,z)$-clustering in any $\ell_{p}$ space for $p\in[1,2)$.

######  Proposition 10.

Suppose we have a (possibly weighted) point set $A$ in $\mathbb{R}^{d}$. Let
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$ with $m\in O(\varepsilon^{-2}\cdot
z^{2}\log n)$ be a terminal embedding for $A$ and let $f(A)$ be the projected
point set. Then if $f(P)\subset f(A)$ is an $\varepsilon$-coreset for $f(A)$,
$P\subset A$ is an $O(\varepsilon)$-coreset for $A$. Conversely, if $P\subset
A$ is an $\varepsilon$-coreset for $A$, then $f(P)\subset f(A)$ is an
$O(\varepsilon)$-coreset for $f(A)$

###### Proof.

We prove the result for the first direction, the other direction is analogous.
Consider an arbitrary solution $S$ in $\mathbb{R}^{d}$. We first notice that
for any point $p\in A$, we have

$(1-\varepsilon/2z)^{z}\cdot\text{cost}(f(p),f(\mathcal{S}))\leq(1-\varepsilon)\cdot\text{cost}(f(p),f(\mathcal{S}))$

and

$(1+\varepsilon/2z)^{z}\cdot\text{cost}(f(p),f(\mathcal{S}))\geq(1+\varepsilon)\cdot\text{cost}(f(p),f(\mathcal{S}))$

Therefore,

$(1-\varepsilon)\cdot\text{cost}(f(p),f(\mathcal{S}))\leq\text{cost}(p,\mathcal{S})\leq(1+\varepsilon)\cdot\text{cost}(f(p),f(\mathcal{S})).$
(32)

Now suppose $f(P)$ is a coreset for $f(A)$, which means for any set of $k$
points $f(S)\subset\mathbb{R}^{m}$

$\displaystyle\left|\sum_{p\in
f(A)}w_{p}\cdot\text{cost}(p,f(\mathcal{S}))-\sum_{q\in
f(P)}w^{\prime}_{q}\cdot\text{cost}(q,f(\mathcal{S}))\right|\leq\varepsilon\cdot\sum_{p\in
f(A)}w_{p}\cdot\text{cost}(p,f(\mathcal{S})),$ (33)

where $w$ and $w^{\prime}$ are the weights assigned to points in $f(A)$ and
$f(P)$, respectively. Let us now consider a solution $S$ in the original
$d$-dimensional space. Since $P$ is a subset of $A$, we have by combining
Equations 32 and 33

$\displaystyle\left|\sum_{p\in
A}w_{p}\cdot\text{cost}(p,\mathcal{S})-\sum_{q\in
P}w^{\prime}_{q}\cdot\text{cost}(p,\mathcal{S})\right|$ $\displaystyle\leq$
$\displaystyle\varepsilon\cdot\sum_{p\in
A}w_{p}\cdot\text{cost}(f(p),f(\mathcal{S}))+\varepsilon\cdot\sum_{q\in
P}w^{\prime}_{q}\cdot\text{cost}(f(q),f(\mathcal{S}))$
$\displaystyle+\left|\sum_{p\in
A}w_{p}\cdot\text{cost}(f(p),f(\mathcal{S}))-\sum_{q\in
P}w^{\prime}_{q}\cdot\text{cost}(f(q),f(\mathcal{S}))\right|$
$\displaystyle\leq$ $\displaystyle 2\varepsilon\cdot\sum_{p\in
A}w_{p}\cdot\text{cost}(f(p),f(\mathcal{S}))+\varepsilon\cdot\sum_{q\in
P}w^{\prime}_{q}\cdot\text{cost}(f(q),f(\mathcal{S}))$ $\displaystyle\leq$
$\displaystyle(3+\varepsilon)\varepsilon\cdot\sum_{p\in
A}w_{p}\cdot\text{cost}(f(p),f(\mathcal{S}))$ $\displaystyle\leq$
$\displaystyle(3+3\varepsilon)\varepsilon\cdot\sum_{p\in
A}w_{p}\cdot\text{cost}(p,\mathcal{S}),$

where the second inequality uses Equation 33 and the triangle inequality and
the last inequality uses Equation 32. ∎

## References

  * [AG06] Ittai Abraham and Cyril Gavoille.  Object location using path separators.  In Eric Ruppert and Dahlia Malkhi, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, USA, July 23-26, 2006, pages 188–197. ACM, 2006.
  * [BBC+19] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn.  Oblivious dimension reduction for _k_ -means: beyond subspaces and the johnson-lindenstrauss lemma.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1039–1050, 2019.
  * [BBH+20] Daniel Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H. C. Jiang, Robert Krauthgamer, and Xuan Wu.  Coresets for clustering in graphs of bounded treewidth, 2020.
  * [BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth.  Learnability and the vapnik-chervonenkis dimension.  J. ACM, 36(4):929–965, 1989.
  * [BEL13] Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang.  Distributed k-means and k-median clustering on general communication topologies.  In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 1995–2003, 2013.
  * [BFL+17] Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F. Yang.  Clustering high dimensional dynamic data streams.  In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 576–585, 2017.
  * [BFLR19] Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus.  Streaming coreset constructions for m-estimators.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, pages 62:1–62:15, 2019.
  * [BJKW19] Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu.  Coresets for ordered weighted clustering.  In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 744–753, 2019.
  * [BJKW21] Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu.  Coresets for clustering in excluded-minor graphs and beyond.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 2679–2696. SIAM, 2021.
  * [BLHK17] Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause.  Uniform deviation bounds for k-means clustering.  In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 283–291. PMLR, 2017.
  * [BLL18] Olivier Bachem, Mario Lucic, and Silvio Lattanzi.  One-shot coresets: The case of k-clustering.  In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, pages 784–792, 2018.
  * [CEM+15] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu.  Dimensionality reduction for k-means clustering and low rank approximation.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 163–172, 2015.
  * [Che09] Ke Chen.  On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications.  SIAM J. Comput., 39(3):923–947, 2009.
  * [CL19] Vincent Cohen-Addad and Jason Li.  On the fixed-parameter tractability of capacitated clustering.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1–41:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [CMK19] Mónika Csikós, Nabil H. Mustafa, and Andrey Kupavskii.  Tight lower bounds on the vc-dimension of geometric set systems.  J. Mach. Learn. Res., 20:81:1–81:8, 2019.
  * [CPP18] Matteo Ceccarello, Andrea Pietracaprina, and Geppino Pucci.  Fast coreset-based diversity maximization under matroid constraints.  In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 81–89, 2018.
  * [CS17] Vincent Cohen-Addad and Chris Schwiegelshohn.  On the local structure of stable clustering instances.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 49–60, 2017\.
  * [EA07] David Eisenstat and Dana Angluin.  The VC dimension of k-fold union.  Inf. Process. Lett., 101(5):181–184, 2007.
  * [EFN17] Michael Elkin, Arnold Filtser, and Ofer Neiman.  Terminal embeddings.  Theor. Comput. Sci., 697:1–36, 2017.
  * [EKM14] David Eisenstat, Philip N. Klein, and Claire Mathieu.  Approximating _k_ -center in planar graphs.  In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 617–627. SIAM, 2014.
  * [FGS+13] Hendrik Fichtenberger, Marc Gillé, Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler.  BICO: BIRCH meets coresets for k-means clustering.  In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 481–492, 2013\.
  * [FKW19] Zhili Feng, Praneeth Kacham, and David P. Woodruff.  Strong coresets for subspace approximation and k-median in nearly linear time.  CoRR, abs/1912.12003, 2019.
  * [FL11] Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 569–578, 2011\.
  * [FMS07] Dan Feldman, Morteza Monemizadeh, and Christian Sohler.  A PTAS for k-means clustering based on weak coresets.  In Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, pages 11–18, 2007.
  * [FS05] Gereon Frahling and Christian Sohler.  Coresets in dynamic geometric data streams.  In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 209–217, 2005.
  * [FSS20] Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering.  SIAM J. Comput., 49(3):601–657, 2020.
  * [GKL03] Anupam Gupta, Robert Krauthgamer, and James R. Lee.  Bounded geometries, fractals, and low-distortion embeddings.  In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 534–543, 2003\.
  * [HCB16] Jonathan Huggins, Trevor Campbell, and Tamara Broderick.  Coresets for scalable bayesian logistic regression.  In Advances in Neural Information Processing Systems, pages 4080–4088, 2016.
  * [HJLW18] Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu.  Epsilon-coresets for clustering (with outliers) in doubling metrics.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 814–825, 2018\.
  * [HJV19] Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi.  Coresets for clustering with fairness constraints.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 7587–7598, 2019.
  * [HK07] Sariel Har-Peled and Akash Kushal.  Smaller coresets for k-median and k-means clustering.  Discrete & Computational Geometry, 37(1):3–19, 2007.
  * [HM01] Pierre Hansen and Nenad Mladenovic.  J-m${}_{\mbox{eans}}$: a new local search heuristic for minimum sum of squares clustering.  Pattern Recognition, 34(2):405–413, 2001.
  * [HM04] Sariel Har-Peled and Soham Mazumdar.  On coresets for k-means and k-median clustering.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 291–300, 2004.
  * [HV20] Lingxiao Huang and Nisheeth K. Vishnoi.  Coresets for clustering in euclidean spaces: importance sampling is nearly optimal.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1416–1429. ACM, 2020.
  * [IMGR20] Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, and Alireza Rezaei.  Composable core-sets for determinant maximization problems via spectral spanners.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1675–1694. SIAM, 2020.
  * [IMMM14] Piotr Indyk, Sepideh Mahabadi, Mohammad Mahdian, and Vahab S. Mirrokni.  Composable core-sets for diversity and coverage maximization.  In Richard Hull and Martin Grohe, editors, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’14, Snowbird, UT, USA, June 22-27, 2014, pages 100–108. ACM, 2014.
  * [LL06] Yi Li and Philip M. Long.  Learnability and the doubling dimension.  In Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, pages 889–896, 2006.
  * [LLS01] Yi Li, Philip M. Long, and Aravind Srinivasan.  Improved bounds on the sample complexity of learning.  J. Comput. Syst. Sci., 62(3):516–527, 2001.
  * [LN17] Kasper Green Larsen and Jelani Nelson.  Optimality of the Johnson-Lindenstrauss Lemma.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 633–638, 2017.
  * [LS10] Michael Langberg and Leonard J. Schulman.  Universal $\varepsilon$-approximators for integrals.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 598–607, 2010.
  * [Mat00] Jirí Matousek.  On approximate geometric k-clustering.  Discrete & Computational Geometry, 24(1):61–84, 2000.
  * [MJF19] Alaa Maalouf, Ibrahim Jubran, and Dan Feldman.  Fast and accurate least-mean-squares solvers.  In Advances in Neural Information Processing Systems, pages 8307–8318, 2019.
  * [MMK18] Alejandro Molina, Alexander Munteanu, and Kristian Kersting.  Core dependency networks.  In Sheila A. McIlraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3820–3827. AAAI Press, 2018.
  * [MMMR18] Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn.  Nonlinear dimension reduction via outer bi-lipschitz extensions.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1088–1101, 2018.
  * [MMR19] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn.  Performance of johnson-lindenstrauss transform for _k_ -means and _k_ -medians clustering.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1027–1038, 2019.
  * [MP04] Ramgopal R. Mettu and C. Greg Plaxton.  Optimal time bounds for approximate clustering.  Mach. Learn., 56(1-3):35–60, 2004.
  * [MS18] Alexander Munteanu and Chris Schwiegelshohn.  Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms.  Künstliche Intell., 32(1):37–53, 2018.
  * [MSSW18] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff.  On coresets for logistic regression.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6562–6571, 2018.
  * [NN19] Shyam Narayanan and Jelani Nelson.  Optimal terminal dimensionality reduction in euclidean space.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1064–1069. ACM, 2019.
  * [Pol12] David Pollard.  Convergence of stochastic processes.  Springer Science & Business Media, 2012.
  * [SSS19] Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler.  Fair coresets and streaming algorithms for fair k-means.  In Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers, pages 232–251, 2019.
  * [SW18] Christian Sohler and David P. Woodruff.  Strong coresets for k-median and subspace approximation: Goodbye dimension.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 802–813, 2018\.
  * [T+96] Michel Talagrand et al.  Majorizing measures: the generic chaining.  The Annals of Probability, 24(3):1049–1103, 1996.
  * [Vit85] Jeffrey Scott Vitter.  Random sampling with a reservoir.  ACM Trans. Math. Softw., 11(1):37–57, 1985.

##  Appendix A Missing Proof

See 1

###### Proof.

The proof of the first inequality is appears in [MMR19], Corollary A.2.

For the second part, let $S(a),S(b)$ be the closest point to $a$ and $b$ from
$S$, and assume that $d(b,S)\leq d(a,S)$. Then:

$\displaystyle d(a,S)^{z}$ $\displaystyle\leq d(a,S(b))^{z}$
$\displaystyle\leq\left(1+\frac{\varepsilon}{2z}\right)^{z-1}\cdot
d(b,S(b))^{z}+\left(1+\frac{2z}{\varepsilon}\right)^{z-1}\cdot d(a,b)^{z}$
$\displaystyle\leq(1+\varepsilon)\cdot
d(b,S(b))^{z}+\left(1+\frac{2z}{\varepsilon}\right)^{z-1}\cdot d(a,b)^{z}$
$\displaystyle\leq d(b,S)^{z}+\varepsilon\cdot
d(a,S(a))^{z}+\left(1+\frac{2z}{\varepsilon}\right)^{z-1}\cdot d(a,b)^{z},$

and so

$\left|d(a,S)^{z}-d(b,S)^{z}\right|=d(a,S)^{z}-d(b,S)^{z}\leq\varepsilon\cdot
d(a,S)^{z}+\left(\frac{2z+\varepsilon}{\varepsilon}\right)^{z-1}d(a,b)^{z}.$

In the other case, when $d(a,S)\leq d(b,S)$:

$\displaystyle d(b,S)^{z}$ $\displaystyle\leq d(b,S(a))^{z}$
$\displaystyle\leq\left(1+\frac{\varepsilon}{2z}\right)^{z-1}\cdot
d(a,S(a))^{z}+\left(1+\frac{2z}{\varepsilon}\right)^{z-1}\cdot d(a,b)^{z}$
$\displaystyle\leq(1+\varepsilon)\cdot
d(a,S)^{z}+\left(1+\frac{2z}{\varepsilon}\right)^{z-1}\cdot d(a,b)^{z},$

and so

$\left|d(a,S)^{z}-d(b,S)^{z}\right|=d(b,S)^{z}-d(a,S)^{z}\leq\varepsilon\cdot
d(a,S)^{z}+\left(\frac{2z+\varepsilon}{\varepsilon}\right)^{z-1}d(a,b)^{z}.$

∎

##  Appendix B A Coreset of Size $k^{2}\varepsilon^{-2}$

In this section, we show how to trade a factor $\varepsilon^{-z}$ for a factor
$k$ in the coreset size.

######  Lemma 29.

Let $(X,\text{dist})$ be a metric space, $P$ be a set of points, $k,z$ two
positive integers and $\mathcal{A}$ a set of $O(k)$ centers such that each for
each cluster with center $c$ induced by $\mathcal{A}$, all points of the
cluster are at distance between
$\left(\frac{\varepsilon}{z}\right)^{2}\Delta_{C}$ and
$\left(\frac{z}{\varepsilon}\right)^{2}\Delta_{C}$, for some $\Delta_{C}$.

Suppose there exists an $\mathcal{A}$-approximate centroid set $\mathbb{C}$
for $P$.

Then, there exists an algorithm running in time $O(|P|)$ that constructs a set
$\Omega$ of size $O(k\cdot
2^{O(z)}\frac{\log^{3}(1/\varepsilon)}{\varepsilon^{2}}\left(k\log
k+k\log|\mathbb{C}|+\log(1/\pi)\right)$ such that, with probability $1-1/\pi$,
for any set $\mathcal{S}$ of $k$ centers,

$\left|\text{cost}(\mathcal{S})-\text{cost}(\Omega,\mathcal{S})\right|=O(\varepsilon)\text{cost}(\mathcal{S}).$

Suppose we initially computed a set of $k^{\prime}$ centers $\mathcal{A}$. Our
aim is to define a sampling distribution that approximates the cost of any
solution $\mathcal{S}$ with high probability. While the basic idea is related
to importance sampling (i.e. sampling proportionate to
$\text{cost}(p,\mathcal{A})$), we add a few modifications that are crucial.

Compared to the framework described in the main body, we change slightly the
definition of ring. For every cluster $\mathcal{C}_{i}$ of $\mathcal{A}$, we
partition the points of $\mathcal{C}_{i}$ into rings $R_{i,j}$ from between
distances $[\left(\frac{\varepsilon}{z}\right)^{2}\Delta_{C}\cdot
2^{j},\left(\frac{\varepsilon}{z}\right)^{2}\Delta_{C}\cdot 2^{j+1}]$, for
$j\in\\{1,\ldots 4z\log(z/\varepsilon)\\}$.

The algorithm is as follows: from every $R_{i,j}$, sample $\delta$ points
uniformly at random (if $|R_{i,j}|\leq\delta$, simply add the whole
$R_{i,j}$).

The analysis of this algorithm follows the same line as the main one. Rings
are divided into tiny, interesting and huge types; tiny and huge are dealt
with as in Lemmas 5 and 7, and interesting points slightly differently.

From the definition of $R_{i,j}$, we immediately get the following
observation.

######  Fact 6.

For every cluster we have at most $O(z\cdot\log z/\varepsilon)$ non-empty
rings in total.

Given a solution $\mathcal{S}$, we consider the groups
$I_{i,j,\ell}\subset\mathcal{C}_{i}$ consisting of the points of $R_{i,j}$
served in $\mathcal{S}$ by a center at distance $[\varepsilon\cdot
2^{\ell},\varepsilon\cdot 2^{\ell+1}]$. As before, we let
$\text{cost}(I_{i,j,\ell},\mathcal{S})=\sum_{p\in
I_{i,j,\ell}}\text{cost}(p,\mathcal{S})$ and
$\text{cost}(I_{j,\ell},\mathcal{S})=\sum_{i=1}^{k^{\prime}}\text{cost}(I_{i,j,\ell},\mathcal{S})$.

Our analysis will distinguish between three cases:

  1. 1.

$\ell\leq j+\log\varepsilon$, in which case we say that $I_{i,j,\ell}$ is
_tiny_.

  2. 2.

$j\cdot\log\varepsilon\leq\ell\leq j+\log(4z/\varepsilon)$, in which case we
say $I_{i,j,\ell}$ is _interesting_.

  3. 3.

$\ell\geq j+\log(16z/\varepsilon)$, in which case we say $I_{i,j,\ell}$ is
_huge_.

We first consider the huge case. For this, we show that the weight of every
ring is preserved with high probability, which implies that the huge groups
are well approximated.

######  Lemma 30.

It holds that, for any $R_{i,j}$ and for all solutions $S$ with at least one
non-empty huge group $I_{i,j,\ell}$

$\left|\text{cost}(R_{i,j},\mathcal{S})-\sum_{p\in\Omega\cap
R_{i,j}}\frac{|R_{i,j}|}{\delta}\cdot\text{cost}(p,\mathcal{S})\right|\leq
3\varepsilon\cdot\text{cost}(R_{i,j},\mathcal{S}).$

###### Proof.

Fix a ring $R_{i,j}$ and let $I_{i,j,\ell}$ be a huge group. First, the weight
of $R_{i,j}$ is preserved in $\Omega$: since $\delta$ points are sampled from
$R_{i,j}$, it holds that

$\sum_{p\in\Omega\cap R_{i,j}}\frac{|R_{i,j}|}{\delta}=|R_{i,j}|$

Now, let $\mathcal{S}$ be a solution, and $p\in I_{i,j,\ell}$ with
$I_{i,j,\ell}$ being huge. This implies, for any $q\in R_{i,j}$:
$\text{cost}(p,q)\leq(2\cdot\varepsilon\cdot 2^{j+1})^{z}\leq
4^{z}\cdot\varepsilon^{z}\cdot
2^{(\ell-\log(16z/\varepsilon))z}\leq\left(\frac{\varepsilon}{4z}\right)^{z}\cdot\text{cost}(p,\mathcal{S})$.
By Lemma 1, we have therefore for any point $q\in R_{i,j}$

$\displaystyle\text{cost}(p,\mathcal{S})$ $\displaystyle\leq$
$\displaystyle\left(1+\varepsilon/2z\right)^{z-1}\text{cost}(q,\mathcal{S})+\left(1+2z/\varepsilon\right)^{z-1}\text{cost}(p,q)$
$\displaystyle\leq$
$\displaystyle\left(1+\varepsilon\right)\text{cost}(q,\mathcal{S})+\varepsilon\cdot\text{cost}(p,\mathcal{S})$
$\displaystyle\Rightarrow\text{cost}(q,\mathcal{S})$ $\displaystyle\geq$
$\displaystyle\frac{1-\varepsilon}{1+\varepsilon}\text{cost}(p,S)\geq(1-2\varepsilon)\text{cost}(p,\mathcal{S})$

Moreover, by a similar calculation, we can also derive an upper bound of
$\text{cost}(q,\mathcal{S})\leq\text{cost}(p,\mathcal{S})\cdot(1+2\varepsilon)$.
Hence, combined with $\sum_{p\in\Omega\cap
R_{i,j}}\frac{|R_{i,j}|}{\delta}=|R_{i,j}|$, this is sufficient to approximate
$\text{cost}(R_{i,j},\mathcal{S})$.

Therefore, the cost of $R_{i,j}$ is well approximated for any solution
$\mathcal{S}$ such that there is a non-empty huge group $I_{i,j,\ell}$. ∎

Next, we consider the interesting cases. The main observation here is that
there are only $O(\log 1/\varepsilon)$ many rings per cluster, hence a coarser
estimation using Bernstein’s inequality is actually sufficient to bound the
cost.

######  Lemma 31.

Consider an $R_{i,j}$ and any solution $\mathcal{S}$ such that all huge
$I_{i,j,\ell}$ are empty. It holds with probability at least
$1-\log(z/\varepsilon)\exp(-\frac{\varepsilon^{2}}{2\cdot
16^{z}\log^{2}z/\varepsilon}\cdot\delta)$ that, for all interesting
$I_{i,j,\ell}$:

$\displaystyle\left|\text{cost}(I_{i,j,\ell},\mathcal{S})-\sum_{p\in
I_{i,j,\ell}\cap\Omega}\text{cost}(p,\mathcal{S})\cdot\frac{|R_{i,j}|}{\delta}\right|\leq\frac{\varepsilon}{\log(z/\varepsilon)}\cdot\left(\text{cost}(R_{i,j},\mathcal{A})+\text{cost}(R_{i,j},\mathcal{S})\right).$

###### Proof.

We start by bounding $|R_{i,j}|\cdot(\varepsilon\cdot 2^{\ell})^{z}$ in terms
of $\text{cost}(R_{i,j},\mathcal{S})+\text{cost}(R_{i,j},\mathcal{A})$.

If $I_{i,j,\ell}$ for some $\ell\geq j+3$ is non-empty, then $\varepsilon\cdot
2^{\ell}-\varepsilon\cdot 2^{j+2}\leq d(q,\mathcal{S})$, for any point $q$.
Hence, $|R_{i,j}|\cdot(\varepsilon\cdot
2^{\ell})^{z}\leq\text{cost}(R_{i,j},\mathcal{S})\cdot 2^{z}$. If $\ell\leq
j+2$, then $|R_{i,j}|\cdot(\varepsilon\cdot
2^{\ell})^{z}\leq|R_{i,j}|\cdot(\varepsilon\cdot
2^{j+2})^{z}\leq\text{cost}(R_{i,j},\mathcal{A})\cdot 4^{z}$. Putting both
bounds together, we have

$|R_{i,j}|\cdot(\varepsilon\cdot 2^{\ell})^{z}\leq
4^{z}(\text{cost}(R_{i,j},\mathcal{S})+\text{cost}(R_{i,j},\mathcal{A}))$ (34)

Since we aim to apply Bernstein’s inequality, we now require a bound on the
second moment of our cost estimator. We have for a single randomly chosen
point $P$:

$\mathbb{E}\left[\sum_{p\in I_{i,j,\ell}\cap
P}\text{cost}(p,\mathcal{S})\cdot|R_{i,j}|\right]=\text{cost}(I_{i,j,\ell},\mathcal{S})$

and

$\displaystyle\mathbb{E}\left[\left(\sum_{p\in I_{i,j,\ell}\cap
P}\text{cost}(p,\mathcal{S})\cdot|R_{i,j}|\right)^{2}\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{p\in I_{i,j,\ell}\cap
P}\text{cost}(p,\mathcal{S})^{2}\cdot|R_{i,j}|^{2}\right]\text{ since }|P|=1$
(35) $\displaystyle=$ $\displaystyle\sum_{p\in I_{i,j,\ell}\cap
P}\text{cost}(p,\mathcal{S})^{2}\cdot|R_{i,j}|\leq|R_{i,j}|\cdot|I_{i,j,\ell}|\cdot(\varepsilon
2^{\ell})^{2z}4^{z}$ $\displaystyle\leq$
$\displaystyle\text{cost}(I_{i,j,\ell},\mathcal{S})\cdot(\text{cost}(R_{i,j},\mathcal{S})+\text{cost}(R_{i,j},\mathcal{A}))\cdot
16^{z}$

where the final equation follows from by lower bounding the cost in
$\mathcal{S}$ of any point in $I_{i,j,\ell}$ with $(\varepsilon\cdot
2^{\ell})^{z}$ and using Equation 34.

Furthermore, by the same reasoning and again using Equation 34, we have the
upper bound $M$ on the (weighted) cost in $\mathcal{S}$ of every sampled point
in every ring:

$M\leq(\varepsilon\cdot
2^{\ell+1})^{z}\cdot|R_{i,j}|\leq(\text{cost}(R_{i,j},\mathcal{S})+\text{cost}(R_{i,j},\mathcal{A}))\cdot
8^{z}$ (36)

Applying Bernstein’s inequality and Equations 35 and 36, we now have

$\displaystyle\mathbb{P}\left[\left|\delta\cdot\text{cost}(I_{i,j,\ell},\mathcal{S})-\sum_{p\in
I_{i,j,\ell}\cap\Omega}\text{cost}(p,\mathcal{S})\cdot|R_{i,j}|\right|>\frac{\varepsilon\cdot\delta}{r}\cdot(\text{cost}(R_{i,j},\mathcal{S})+\text{cost}(R_{i,j},\mathcal{A}))\right]$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\frac{\varepsilon^{2}\cdot\delta}{r^{2}}\cdot(\text{cost}(R_{i,j},\mathcal{S})+\text{cost}(R_{i,j},\mathcal{A}))}{\text{cost}(I_{i,j,\ell},\mathcal{S})\cdot
16^{z}+\frac{4\varepsilon}{3r}\cdot(\text{cost}(R_{i,j},\mathcal{S})+\text{cost}(R_{i,j,\ell}))\cdot
8^{z}}\right)\leq\exp\left(-\frac{\varepsilon^{2}\cdot\delta}{2r^{2}16^{z}}\right),$

where the last line uses
$\text{cost}(I_{i,j,\ell},\mathcal{S})\leq\text{cost}(R_{i,j},\mathcal{S})$.
Applying a union bound over all $r$ interesting sets $I_{i,j,\ell}$, we obtain
the above guarantee for all $I_{i,j,\ell}$ simultaneously with probability

$1-r\cdot\exp\left(-\frac{\varepsilon^{2}\cdot\delta}{2r^{2}16^{z}}\right).$

∎

Finally, we conclude:

###### Proof of Lemma 29.

As in the proof of Lemma 2, we decompose
$|\text{cost}(\mathcal{S})-\text{cost}(\Omega,\mathcal{S})|$ into terms
corresponding to points of tiny, interesting or huge groups. We only sketch
the proof here, the details are the same as for Lemma 2. We condition on event
$\mathcal{E}$ happening. Let $\mathcal{S}$ be a set of $k$ points, and
$\tilde{\mathcal{S}}\in\mathbb{C}^{k}$ that approximates best $\mathcal{S}$,
as given by the definition of $\mathbb{C}$ (see Definition 1). This ensures
that for all points $p$ with
$\text{dist}(p,\mathcal{S})\leq\frac{8z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$
or
$\text{dist}(p,\tilde{\mathcal{S}})\leq\frac{8z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$
, we have
$|\text{cost}(p,\mathcal{S})-\text{cost}(p,\tilde{\mathcal{S}})|\leq\varepsilon(\text{cost}(p,\mathcal{S})+\text{cost}(p,\mathcal{A}))$.

Our first step is to deal with points that have
$\text{dist}(p,\mathcal{S})>\frac{8z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$,
using Lemma 30. All other points have distance well approximated by
$\tilde{\mathcal{S}}$. Then, we can apply Lemma 5 and Lemma 31 to
$L_{\tilde{\mathcal{S}}}$, since all points in $L_{\tilde{\mathcal{S}}}$ have
$\text{dist}(p,\tilde{\mathcal{S}})\leq\frac{4z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$,
and so
$\text{dist}(p,\mathcal{S})\leq\frac{8z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$
and were not removed by the previous step. Remaining points are those which
have
$\text{dist}(p,\tilde{\mathcal{S}})>\frac{4z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$
and
$\text{dist}(p,\mathcal{S})\leq\frac{8z}{\varepsilon}\cdot\text{dist}(p,\mathcal{A})$,
i.e., their distance is preserved in $\tilde{\mathcal{S}}$ and they are huge
with respect to $\tilde{\mathcal{S}}$. We apply Lemma 7 to them as well. ∎

Combining this lemma and Lemma 4 gives an analogous to Theorem 1. Now, using
this lemma instead of Theorem 1 in all proofs of section Section 8 gives bound
with a factor $k$ instead of a $\varepsilon^{-z}$.