# Parameterized Approximation for Robust Clustering
in Discrete Geometric Spaces

Fateme Abbasi11footnotemark: 1 Sandip Banerjee11footnotemark: 1 Jarosław
Byrka111University of Wrocław, Poland<EMAIL_ADDRESS><EMAIL_ADDRESS>Ameet Gadekar222Aalto University, Espoo, Finland
<EMAIL_ADDRESS>Kamyar Khodamoradi333University
of British Columbia, Canada<EMAIL_ADDRESS>Roohani
Sharma55footnotemark: 5 Joachim Spoerhase444Max Planck Institute for
Informatics, Saarbrücken, Germany ({rsharma,jspoerha}@mpi-inf.mpg.de)${}^{\;}$
555The University of Sheffield, United Kingdom<EMAIL_ADDRESS>
###### Abstract

We consider the well-studied Robust $(k,z)$-Clustering problem, which
generalizes the classic $k$-Median, $k$-Means, and $k$-Center problems. Given
a constant $z\geq 1$, the input to Robust $(k,z)$-Clustering is a set $P$ of
$n$ weighted points in a metric space $(M,\delta)$ and a positive integer $k$.
Further, each point belongs to one (or more) of the $m$ many different groups
$S_{1},S_{2},\ldots,S_{m}$. Our goal is to find a set $X$ of $k$ centers such
that $\max_{i\in[m]}\sum_{p\in S_{i}}w(p)\delta(p,X)^{z}$ is minimized.

This problem arises in the domains of robust optimization [Anthony, Goyal,
Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness. For
polynomial time computation, an approximation factor of $O(\log m/\log\log m)$
is known [Makarychev, Vakilian, COLT $2021$], which is tight under a plausible
complexity assumption. Since the hardness holds even in the line metrics,
recent research has focused on obtaining constant-factor approximations in
parameterized running time. In particular, there is a
$(3^{z}+\epsilon)$-approximation algorithm running in
$f(k,\epsilon)\textsf{poly}(n,m)$ time (i.e., FPT in parameter $k$), which is
tight under GAP-ETH [Goyal, Jaiswal, Inf. Proc. Letters, 2023].

Motivated by the tight lower bounds for general discrete metrics, we focus on
_geometric_ spaces such as the (discrete) high-dimensional Euclidean setting
and metrics of low doubling dimension, which play an important role in data
analysis applications. First, for a universal constant $\eta_{0}>0.0006$, we
devise a $3^{z}(1-\eta_{0})$-factor FPT approximation algorithm for discrete
high-dimensional Euclidean spaces thereby bypassing the lower bound for
general metrics. We complement this result by showing that even the special
case of $k$-Center in dimension $\Theta(\log n)$ is $(\sqrt{3/2}-o(1))$-hard
to approximate for FPT algorithms. In particular, it does not admit an
efficient parameterized approximation scheme (EPAS)—a
$(1+\epsilon)$-approximation algorithm with running time
$f(k,\epsilon)\textsf{poly}(m,n)$. Finally, we complete the FPT approximation
landscape by designing an EPAS for Robust $(k,z)$-Clustering when the
dimension is sub-logarithmic. Our EPAS works also for the metric of sub-
logarithmic doubling dimension.

##  1 Introduction

Clustering is a crucial method in the analysis of massive datasets and has
widespread applications in operations research and machine learning. As a
consequence, optimization problems related to clustering have received
significant attention from the theoretical computer science community over the
years. Within the framework of center-based clustering, $k$-Center, $k$-Means,
and $k$-Median [15, 16, 8, 3, 17] are the most fundamental problems.

A general notion that captures various classic clustering problems is referred
to as $(k,z)$-Clustering in the literature, where $z\geq 1$ is a constant. In
this type of problem, the input is a set of points $P$, a set of facilities
$F$, a metric $\delta$ on $P\cup F$, and a positive integer $k$. The goal is
to find a set $C\subseteq F$ of $k$ facilities (centers) that minimizes the
following cost function:

$cost(C)=\sum_{p\in P}cost(p,C)$

where $cost(p,C)=\delta(p,C)^{z}$ and $\delta(p,C)=\min_{c\in C}\delta(p,c)$.
Note that $(k,z)$-Clustering encapsulates the classical $k$-Median, and
$k$-Means for $z=1$ and $z=2$, respectively .

Center-based clustering has cemented its place as an unsupervised learning
method that has proven effective in modeling a variety of real-world problem.
In most of the practical machine learning applications however, it is observed
that the input data is rarely of high quality .

To tackle this challenge, we study a robust version of $(k,z)$-Clustering in
this paper which can handle uncertainty in the input: Consider a situation
where we do not have complete knowledge about the clients that will be served.
In order to perform well despite this uncertainty, Anthony et al. [4] defined
a concept of robustness for the $k$-Median problem. In this paper, we address
the following robust version of the $(k,z)$-Clustering problem. Formally, for
a constant $z\geq 1$, the Robust $(k,z)$-Clustering problem is defined as
follows:

Robust $(k,z)$-Clustering Input: Instance $(P,F,\delta)$ with $\delta$ being a
metric on $P\cup F$, positive integer $k$, a weight function $w\colon
P\rightarrow{\mathbb{R}}_{+}$, and $m$ groups $S_{1},\ldots,S_{m}$ such that
$S_{i}\subseteq P,P=\cup_{i\in[m]}S_{i}$. Output: A $k$-element subset
$X\subseteq F$ that minimizes $\max_{i\in[m]}\sum_{p\in
S_{i}}w(p)\delta(p,X)^{z}$ .

Let $n=|P|$. We remark that, in addition to generalizing $k$-Median and
$k$-Means, the Robust $(k,z)$-Clustering problem encapsulates $k$-Center, when
each group contains a distinct singleton point. A similar objective has been
studied in the context of fairness, in which we aim at creating a solution
that will be appropriate for each of the specified groups of people. This
problem is known in the literature as Socially Fair $k$-Median, recently
introduced independently by Abbasi et al. [2] and Ghadiri et al. [11].

While $k$-Means, $k$-Median, and $k$-Center admit constant-factor
approximations, it is not very surprising that Robust $(k,z)$-Clustering is
harder due to its generality: Makarychev and Vakilian [18] design a
polynomial-time $\mathcal{O}\left(\log m/\log\log m\right)$-approximation
algorithm, which is tight under a standard complexity assumption [6]666Note
that they proved this factor for Robust $k$-Median.. As this precludes the
existence of efficient constant-factor approximation algorithms, recent works
have focused on designing constant factor _parameterized_ (FPT) approximation
algorithms777 Throughout the paper, parameterization refers to the natural
parameter $k$.. Along these lines, an FPT time
$(3^{z}+\epsilon)$-approximation algorithm has been proposed and shown to be
tight under Gap-ETH [13]. When allowing a parameterization on the number of
groups $m$ (instead of $k$), Ghadiri et al. designed a
$(5+2\sqrt{6}+\epsilon)^{2}$-approximation algorithm in
$n^{\mathcal{O}\left(m^{2}\right)}$ time [12].

Motivated by the tight lower bounds for general discrete metrics, we focus on
_geometric_ spaces such as the (discrete) high-dimensional Euclidean setting
and metrics of low doubling dimension. Geometric spaces have a particular
importance in real-world applications because, often, data can be represented
via a (potentially large) collection of numerical attributes, that is, by
vectors in a (possibly high-dimensional) geometric space. For example, in the
bag-of-words model a document is represented by a vector where each coordinate
specifies the frequency of a given word in that document. Such representations
naturally lead to very high-dimensional data. A setting of particular interest
is the discrete high-dimensional _Euclidean space_ , that is, when $P$ and $F$
are finite subsets of $\mathbb{R}^{d}$ , and $\delta(x,y)=||x-y||_{2}$ for
$x,y\in\mathbb{R}^{d}$.

Goyal and Jaiswal [13] rule out FPT-approximation algorithms with factor
$3^{z}-o(1)$ for Robust $(k,z)$-Clustering in general discrete metrics, this
does not automatically hold true for the important case of geometric spaces
such as the (discrete) high-dimensional Euclidean space or metrics of low
doubling dimension.

In this paper, we address two main research questions related to discrete
high-dimensional space and low-dimension doubling dimension, respectively.
Regarding the high-dimensional setting we ask the following.

######  Question 1.1.

Can the geometric properties of discrete high-dimensional space be leveraged
by FPT approximation algorithms for Robust $(k,z)$-Clustering, bypassing the
lower bound of $3^{z}-o(1)$ by Goyal and Jaiswal [13] for general discrete
metric spaces?

In this paper, we answer the above question affirmatively by designing an FPT
approximation algorithm with a ratio slightly below the barrier of $3^{z}$.
Further, on the negative side, we rule out the existence of approximation
schemes in this setting, by showing that it is $W[1]$-hard to approximate even
the special case of Discrete $k$-Center in $\mathbb{R}^{O(\log n)}$ better
than factor $\sqrt{3/2}$. Consequently, to complete the landscape, we ask if
there is an efficient parameterized approximation scheme (EPAS), that provides
a $(1+\epsilon)$-approximation running in time
$f(k,\epsilon)\textsf{poly}(m,n)$, for the problem in lower dimension.

######  Question 1.2.

Does there exist an efficient parameterized approximation scheme (EPAS) for
Robust $(k,z)$-Clustering in Euclidean metrics of sub-logarithmic dimension?

Indeed, we answer the question positively, and in fact, we show an EPAS for
Robust $(k,z)$-Clustering in doubling metrics of sub-logarithmic dimensions
that generalize the Euclidean metric.

###  1.1 Our Contributions

In this paper, we consider Robust $(k,z)$-Clustering in _discrete_ geometric
spaces. We start with a negative result by showing that even the special case
of $k$-Center does not admit an EPAS. This hardness holds for any $\ell_{q}$
metrics and even in $\mathbb{R}^{\mathcal{O}\left(\log n\right)}$. More
formally, we prove the following theorem.

######  Theorem 1.1 (Hardness of Discrete Euclidean).

For any constant positive integer $q$, it is $W[1]$-hard to approximate the
discrete $k$-Center problem in $\mathbb{R}^{O(\log n)}$ under the $\ell_{q}$
metrics to within a factor of $(3/2-\eta)^{1/q}$ for any positive constant
$\eta>0$.

Our hardness result can be contrasted with the continuous setting, in which
the set $F$ of potential cluster centers equals continuous space
$\mathbb{R}^{d}$. The continuous setting admits an EPAS for Robust
$(k,z)$-Clustering in the high-dimensional Euclidean space [1]. We further
remark that the algorithm of [1] also yields an EPAS in doubling metrics but
only of dimension $d=o(\log\log n)$, while Theorem 1.1 rules out EPAS for
$d=\Omega(\log n)$. We complete the landscape by designing an EPAS for the
problem in the doubling metrics of dimension $d=o(\log n)$.

######  Theorem 1.2 (EPAS for Doubling Metric of sub-logarithmic dimension).

There is an algorithm that, given an instance of Robust $(k,z)$-Clustering in
a metric of doubling dimension $d$, computes $(1+\epsilon)$-approximate
solution for the instance, for every $\epsilon>0$, in time
$f(k,d,\epsilon,z)\textsf{poly}(m,n)$, where
$f(k,d,\epsilon,z)=\left(\left(\frac{2^{z}}{\epsilon}\right)^{d}k\log
k\right)^{\mathcal{O}\left(k\right)}$.

Finally, motivated by a factor-$(3^{z}-o(1))$ hardness of FPT approximation
for Robust $(k,z)$-Clustering in general metrics [13], a natural question is
whether the structures of Euclidean spaces can be leveraged to obtain better
results in high dimensions. We answer this question affirmatively as follows.

######  Theorem 1.3 (High Dimensional Setting).

There exists a universal constant $\eta_{0}>0.0006$ such that for any constant
positive integer $z$, there is a factor $3^{z}(1-\eta_{0})$ FPT approximation
algorithm for Robust $(k,z)$-Clustering in discrete ${\mathbb{R}}^{d}$ that
runs in time $2^{\mathcal{O}\left(k\log k\right)}\textsf{poly}(m,n)$.

Note that our running time has only polynomial dependency on $d$.

##  2 Overview of Techniques

#### Approximation Scheme for Metrics of Sub-Logarithmic Doubling Dimension.

We will describe our algorithm for $z=1$, since it makes the presentation
easier and at the same time contains almost all of the ideas of the general
case. First we give a high level idea of our algorithm that itself is composed
of two algorithms. Let
$\mathcal{I}=(P,F,\delta,\mathcal{G}=\\{S_{i}\\}_{i\in[m]})$ be an instance of
Robust $(k,z)$-Clustering in a doubling metric of dimension $d$. The first
algorithm creates a “coreset” of the instance by reducing the number of points
in $P$. While this new instance has much fewer points, it still has the same
number of groups. We would like to remark that regular (strong) coresets have
a guarantee that the cost of any feasible solution in the coreset instance is
preserved up to a multiplicative factor of $(1+\epsilon)$, for any arbitrary
$\epsilon>0$. However, our coreset does not give a guarantee that for any
feasible solution $X$, the cost of every group due to $X$ is approximately
preserved. In fact, it only guarantees that, for any feasible solution $X$,
the cost of $X$ is approximately preserved, where the cost of $X$ is the
maximum cost of any group due to $X$. With this coreset instance, we proceed
to the second algorithm. Here, we exploit the fact that the instance is a
coreset instance and hence has small $P$. This allows us to construct enough
balls of facilities whose union contain an optimal solution. Finally, we use
the fact that any ball in the doubling metric can be decomposed into smaller
balls of half radius, which allows us to get arbitrary close to the optimal
solution.

The key insight for the “coreset” algorithm is the following alternate
interpretation of the problem. Given $\mathcal{I}=(P,F,\delta,\mathcal{G})$,
we interpret each group $S\in\mathcal{G}$ as a weight function ${\bf
w}_{S}:P\rightarrow\mathbb{R}_{\geq 0}$ such that ${\bf w}_{S}(p)=w(p)$ for
$p\in S$ and $0$ otherwise. Note that with this interpretation, a point $p\in
P$ can participate with various groups with different weights. Thus, a point
$p\in P$ can now represent any other point $p^{\prime}\in P$ in its proximity
by setting ${\bf w}^{\prime}_{S}(p)={\bf w}_{S}(p)+{\bf w}_{S}(p^{\prime})$
for every group $S\in\mathcal{G}$, where ${\bf w}^{\prime}_{S}(p)$ is the
weight of $p$ in the coreset. In other words, we can delete $p^{\prime}$ and
approximate its contribution to the cost by the contribution of $p$. Note that
the difference due to approximation is only due to the distance between $p$
and $p^{\prime}$. This idea is based on the grid construction approach of
[14]. Let OPT denote the optimal cost of $\mathcal{I}$. We first obtain a good
upper bound on OPT by using some bi-criteria approximation algorithm (for
e.g., see [18]) that opens $\beta k$ facilities $B$ with cost
$\alpha\textsf{OPT}$ for some constants $\alpha,\beta\geq 1$. For each
facility $b_{i}\in B$, we carve a sequence of (initial) balls
$B^{0}_{i},B^{1}_{i},\cdots$ around it, such that $B^{j}_{i}$ has radius
$2^{j}R$, where $R=\frac{\textsf{cost}(B)}{\alpha\tau}$ and
$\tau=\max_{S\in\mathcal{G}}||{\bf w}_{S}||_{1}$. Note that, assuming the
weight aspect ratio is polynomially bounded in $n$, we need to carve out only
$\mathcal{O}\left(\log(\alpha n)\right)$ balls around each $b_{i}$ to
guarantee that every point in $P$ is present in some ball. Next we decompose
each $B^{j}_{i}$ into smaller balls each of radius
$\nicefrac{{\epsilon}}{{40\alpha}}$ fraction of $B^{j}_{i}$. Finally, for
every small ball $b$, we pick an arbitrary but distinct point $p$ and add it
to our coreset $P^{\prime}$ with weight ${\bf w}^{\prime}_{S}(p):={\bf
w}_{S}(p)+\sum_{\hat{p}\in b}{\bf w}_{S}(\hat{p})$ for every group
$S\in\mathcal{G}$ (some more work is required to avoid double counting). We
call such $p$ the representative of all other points $\hat{p}\in b$. Let
$\mathcal{I}^{\prime}=(P^{\prime},F,\delta,\mathcal{G}^{\prime})$ be the
coreset instance. First observe that our decomposition produces same number of
smaller balls ($=1/\epsilon^{\mathcal{O}\left(d\right)}$) in every initial
ball irrespective of their sizes due to doubling metric. Hence
$|P^{\prime}|=\beta\log(\alpha n)/\epsilon^{\mathcal{O}\left(d\right)}$. Now,
let us argue about the guarantee of the coreset. Fix a feasible solution $X$.
Observe that the ball $B^{0}_{i}$ is very small, and hence $p$ and $\hat{p}$
are relatively close to each other, and hence their connection cost to any
feasible solution $X$ is approximately the same. In other words, let
$B^{0}=\cup_{i\in[k]}B^{0}_{i}$, then for $p\in B^{0}$, the difference in the
connection cost of $B^{0}$ is bounded by

$\sum_{p\in B^{0}}{\bf
w}_{S}(p)\delta(p,p^{\prime})\leq\frac{\epsilon}{40\alpha}R\sum_{p\in
B^{0}}{\bf w}_{S}(p)\leq\epsilon\textsf{OPT}/4.$

Now, for larger $B^{j}_{i}$, the distance between $p$ and its representative
$p^{\prime}$ could be very large. However, the crucial observation is that
such $p$ also incurs large connection cost to $B$, and hence its distance to
$p^{\prime}$ can be represented in terms of its connection cost to $B$. In
other words, it can be shown that if $\delta(p,B)>R$, then
$\delta(p,p^{\prime})\leq\frac{\epsilon}{10\alpha}\delta(p,B)$. Hence, the
connection cost of $P\setminus B^{0}$ is bounded by

$\sum_{p\in\\{P\setminus B^{0}\\}}{\bf
w}_{S}(p)\delta(p,p^{\prime})\leq\sum_{p\in\\{P\setminus B^{0}\\}}{\bf
w}_{S}(p)\frac{\epsilon}{10\alpha}\delta(p,B)\leq\epsilon\textsf{OPT}/10.$

Hence, $|\textsf{cost}({\bf w}_{S},X)-\textsf{cost}({\bf
w}^{\prime}_{S},X)|\leq\epsilon\textsf{OPT}$. With some more arguments and
adjustment of parameters, this idea can be extended to Robust
$(k,z)$-Clustering.

Next, we describe the second algorithm that takes as input a coreset instance,
and produces a $(1+\epsilon)$-approximate solution. The idea is based on the
leader guessing approach of [9] that exploits the smaller size of $P$.
Consider some optimal solution $O=(o_{1},\cdots,o_{k})$, and let
$Q=(Q_{1},\cdots,Q_{k})$ be the corresponding clusters. Each cluster $Q_{i}$
can be identified by a closest point $\ell_{i}$ to $o_{i}$ in $P$. Let
$\lambda_{i}:=\delta(\ell_{i},o_{i})$. Then, note that in FPT time we can
guess $\ell_{i}$ and $\lambda_{i}$ for all $i\in[k]$, if $|P|$ is small and
the distance aspect ratio is bounded polynomially. The first one is guaranteed
by our coreset algorithm, and latter is true due to polynomially bounded
weight aspect ratio. Once, we guess $(\ell_{i},\lambda_{i})$ correctly for all
$i\in[k]$, then we can consider the ball $B_{i}={\sf
ball}(\ell_{i},\lambda_{i})$ such that $o_{i}\in B_{i}$. Note that, picking an
arbitrary facility $f$ from each $B_{i}$ already gives factor $3$
approximation since for any point $p$ served by $o_{i}$ in optimal solution is
served by $f$ at distance at most $2\lambda_{i}\leq 2\delta(p,o_{i})$ from
$o_{i}$. To get $(1+\epsilon)$-approximation, we use the fact that in a
doubling metric every ball $B_{i}$ can be decomposed into smaller balls. This
results in $1/\epsilon^{\mathcal{O}\left(d\right)}$ smaller balls each of
radius $\epsilon\lambda_{i}/2$. Hence, in total we check
$1/\epsilon^{\mathcal{O}\left(dk\right)}$ combinations of $k$-sized facility
set such that one combination $(a_{1},\cdots,a_{k}),a_{i}\in F$ is close to
$O$ that is, $\delta(a_{i},o_{i})\leq\epsilon\lambda_{i}/2$ for all $i\in[k]$.

#### Hardness of Discrete $k$-Center

Our proof constructs an instance of the discrete $k$-Center from an instance
of Multi-Colored Independent Set problem, which is known to be $W[1]$-hard. In
Multi-Colored Independent Set, we are given a $k$-partite graph $G$ with a
$k$-partition of the vertices $V_{1},\dots,V_{k}$, and the goal is to
determine if there is an independent set that contains precisely one node from
each set $V_{i}$, $i\in[k]$. The gadget in our construction is a set of nearly
equidistant binary code words. Such code words with relative Hamming distance
roughly $\nicefrac{{1}}{{2}}$ and logarithmic length are known to exist (see
Ta-Shma [19]). The high level idea is as follows. We associate each vertex of
$G$ a unique code word of suitable length $t$. Then, we generate a data point
in $P$ for each vertex and edge of $G$ by using code word(s) associated with
the corresponding vertices. The construction guarantees the following crucial
properties: (i) The Hamming distance between the data points of vertices is
roughly $t$. (ii) The Hamming distance between a data point of vertex $v\in
V_{i}$ and a data point of an edge $e$ is roughly $t$ if $e$ is incident on
$V_{i}\setminus\\{v\\}$ and is roughly $3t/2$ otherwise. (iii) The Hamming
distance between the data points of edges is at least (close to) $3t/2$. Thus,
the construction forces us to we pick data points of vertices as centers in
our solution and guarantees that the optimum cost of the $k$-Center instance
is roughly $t$ if and only if there is an independent set in $G$. As a result,
approximating the cost of the $k$-Center instance better than a (roughly)
$(3/2)^{1/q}$ factor would imply $W[1]=FPT$. That is because the cost of a
$k$-Center instance is the maximum $\ell_{q}$ distance between a data point
and its closest selected center, and hence, approximating this cost better
than the mentioned factor allows us to distinguish between Yes and No cases of
an arbitrary instance of Multi-Colored Independent Set.

#### Constant-Factor Approximation in Euclidean Metrics.

We build on an idea from [13] that gives a factor-$(3^{z}+\epsilon)$ FPT
approximation for the

Robust $(k,z)$-Clustering problem in general metric. Their result crucially
utilizes a simple property of metric spaces, which we call the “projection
lemma”: Let $(Y,\delta)$ be a metric space, and $B\subseteq Y$. Then for any
set $X\subseteq Y$, there exists an assignment $\sigma\colon X\rightarrow B$
such that, for all $x\in X$, we have $\delta(x,\sigma(X))\leq
2\delta(x,X)+\delta(x,B)$.

Intuitively, this lemma allows us to “assign” any set $X$ to
$\sigma(X)\subseteq B$ in a way that distances from points in $Y$ are
approximately preserved (within a factor of $3=2+1$ – the sum of the constants
in front of $\delta(x,X)$ and $\delta(x,B)$ 888Note that a simple projection
of $x$ to $\pi_{B}(x)$, its closest point in $B$, would do the job.) Goyal and
Jaiswal [13] show how to use this lemma to devise a $(3^{z}+\epsilon)$ FPT
approximation algorithm. An obvious way to try to improve this approximation
factor is to reduce the constants in front of the term $\delta(x,X)$ and
$\delta(x,B)$ in the lemma for the case when $\delta$ is a Euclidean metric.
Unfortunately, this straightforward attempt would not work: These constants
are tight even for the line metric (see Figure 1).

We overcome this barrier via two ideas: (i) We allow a larger projection
space, that is, instead of $B$, we project $X$ on a larger set that is
efficiently computable – the points in $F$ closest to the midpoints of pairs
of points in $B$, therefore define the midpoint closure of ${\sf
cl}(B)=B\cup\\{\pi_{F}\left(\frac{b+b^{\prime}}{2}\right):b,b^{\prime}\in
B\\}$; notice that this step crucially exploits the Euclidean space (so that
the midpoints exist); and (ii) we “relax” the requirement and only aim to
upper bound the projection distance among the “far” points in $X$. Given $X$
and $B$, point $x\in Y$ is said to be $\epsilon$-far if
$\delta(x,X)\geq\epsilon\delta(x,B)$ (intuitively, these are the points that
are sufficiently far from $X$ compared to the distance from $B$). We remark
that each idea alone would not be sufficient to get an improved result.

We show that this new assignment property is enough to derive an improved FPT
approximation for Robust $(k,z)$-Clustering in Euclidean space.

##  3 EPAS for Metrics of Sub-Logarithmic Doubling Dimension

In this section, we show an EPAS for Robust $(k,z)$-Clustering in metrics of
sub-logarithmic doubling dimension. This result complements the hardness
result of Section 4 (Theorem 1.1). Towards our goal, we prove the following
result.

See 1.2

Note that the above algorithm runs in FPT time for $d=o(\log n)$. We also
remark that the above result can be extended to the continuous
$\mathbb{R}^{d}$. Throughout this section, we assume that the weight aspect
ratio $\frac{\max_{p\in P}w(p)}{\min_{p^{\prime}\in P}w(p^{\prime})}$ and the
distance aspect ratio $\frac{\max_{p,p^{\prime}\in
P}\delta(p,p^{\prime})}{\min_{p\neq p^{\prime}\in P}\delta(p,p^{\prime})}$ are
bounded by $\textsf{poly}(n)$, some polynomial in $n$. For $p\in P$ and any
number $r\geq 0$, denote by ${\sf ball}(p,r)$ to be the closed ball centered
at $p$ of radius $r$. We prove the theorem in two steps: first, in Section 3.1
we show an algorithm to obtain a “coreset” for the problem, and then, in
Section 3.2 we show how to use this coreset to get the algorithm of Theorem
1.2.

###  3.1 Coreset for Robust $(k,z)$-Clustering

The key idea for constructing coresets for Robust $(k,z)$-Clustering crucially
relies on the following alternate but equivalent definition of the problem. In
this definition, we are given
$\mathcal{I}=(F,P\subset\mathcal{M},\mathcal{W})$, where either
$F=\mathcal{M}$ or $F\subseteq\mathcal{M}$, where $\mathcal{M}$ is doubling
metric of dimension $d$, defined by the metric function $\delta$. A _group_ is
a weight vector ${\bf w}\in\mathcal{W}$ such that ${\bf
w}:P\rightarrow{\mathbb{R}}_{\geq 0}$. Given $X\subseteq F$, the distance
vector ${\boldsymbol{\delta}}_{P}(X)$ is defined as
${{\boldsymbol{\delta}}}_{P}(X)[p]=\delta(p,X)^{z}$, for each $p\in P$. The
cost of $X$ for a group ${\bf w}\in\mathcal{W}$ is defined as $c({\bf
w},X)={\bf w}\cdot{\boldsymbol{\delta}}_{P}(X)$. For a Robust
$(k,z)$-Clustering instance $\mathcal{I}=(F,P,\mathcal{W})$, the cost of $X$
is defined as $\textsf{cost}_{\mathcal{I}}(X)=\max_{{\bf
w}\in\mathcal{W}}\textsf{cost}({\bf w},X)$. The cost of the instance
$\mathcal{I}=(F,P,\mathcal{W})$ is

$\textsf{OPT}_{\mathcal{I}}=\min_{X\subseteq F}\max_{{\bf
w}\in\mathcal{W}}\textsf{cost}({\bf w},X)$

Whenever the instance $\mathcal{I}$ is clear from context, we will just write
OPT. Notice that, in the original Robust $(k,z)$-Clustering, a group is given
by $S\subseteq P$, and this can be captured by weight vector ${\bf w}[p]=0$
for $p\not\in S$ and $w(p)$ otherwise. We prove the following “coreset” for
Robust $(k,z)$-Clustering.

######  Theorem 3.1 (Coreset for Robust $(k,z)$-Clustering).

Given an instance $\mathcal{I}=(F,P,\mathcal{W})$ of Robust $(k,z)$-Clustering
in doubling metric of dimension $d$ and $\epsilon>0$, there is an algorithm
that, in time
$\left(\frac{2^{z}}{\epsilon}\right)^{\mathcal{O}\left(d\right)}\textsf{poly}(n,m)$,
computes $(P^{\prime},\mathcal{W}^{\prime})$ such that $P^{\prime}\subseteq
P:|P^{\prime}|=\left(\frac{2^{z}}{\epsilon}\right)^{\mathcal{O}\left(d\right)}kz\log
n$, and a bijection $\eta:\mathcal{W}\rightarrow\mathcal{W}^{\prime}$ such
that, for all $X\subseteq F$ of size $k$ and ${\bf w}\in\mathcal{W}$, we have

$(1-\epsilon)\textsf{cost}({\bf w},X)\leq\textsf{cost}(\eta({\bf
w}),X)\leq(1+\epsilon)\textsf{OPT}$

We remark that the above theorem yields a coreset of clients, and not of
groups, and hence, the total size of coreset is comparable to the original
instance. However, we will show later that such coreset is sufficient to get a
parameterized approximation scheme with parameters $k$ and $d$.

We would also like to point out that the exponential dependency on $d$ on the
point set size of the coreset is inevitable since Robust $(k,z)$-Clustering
captures $k$-Center, for which such lower bound in known [7, 5]. To see that
our notion of coreset for Robust $(k,z)$-Clustering coincides with the regular
notion of coreset for $k$-Center, note that in this setting each group
contains a single distinct point.

Data: Instance $\mathcal{I}=(F,P,\mathcal{W})$ of Robust $(k,z)$-Clustering,
$(\alpha,\beta)$-bicriteria solution $B$ for $\mathcal{I}$

Result: Coreset $(P^{\prime},\mathcal{W}^{\prime})$ of $(P,\mathcal{W})$

1 Let $P^{\prime}\leftarrow\emptyset$;

2 Let ${\bf w}^{\prime}\in\mathcal{W}=\eta({\bf w})\leftarrow\textbf{0}$ for
${\bf w}\in\mathcal{W}$;

3 Let $\tau\leftarrow\max_{{\bf w}\in\mathcal{W}}||{\bf w}||_{1}$;

4 Let $R=\sqrt[z]{\frac{\textsf{cost}_{\mathcal{I}}(B)}{\alpha\tau}}$;

5 For each $b_{i}\in B$ for $j\in\\{0,1,\cdots,\lceil
2\log\alpha\Delta\rceil\\}$, let $\mathcal{B}^{j}_{i}={\sf
ball}(b_{i},2^{j}R)$, and let
$\mathcal{Q}^{j}_{i}=\mathcal{B}^{j}_{i}-\mathcal{B}^{j-1}_{i}$ with
$\mathcal{Q}^{0}_{i}=\mathcal{B}^{0}_{i}$;

6

Decompose each ball $\mathcal{B}^{j}_{i}$ into balls of radius each
$\frac{\epsilon}{\alpha 3^{z+2}}2^{j}R$ ;

// e.g., use Lemma A.1

7

8Associate each point $p\in P$ to a smallest ball containing $p$ breaking ties
arbitrary;

9

10foreach  _$i\in[k]$_ do

11 foreach  _ $j\in\\{0,1,\cdots,\lceil 2\log\alpha\Delta\rceil\\}$_ do

12 foreach  _smaller ball $t$ of $\mathcal{B}^{j}_{i}$_ do

13 if  _$\exists p\in t\cap Q^{j}_{i}$_ then

14 $P^{\prime}\leftarrow P^{\prime}\cup p$ ;

15 For each ${\bf w}\in\mathcal{W}$, $\eta({\bf w})[p]:=\sum_{p^{\prime}\in
t\cap\mathcal{Q}^{j}_{i}}{\bf w}[p^{\prime}]$;

16 break;

17

18 end if

19

20 end foreach

21

22 end foreach

23

24 end foreach

return _$(P^{\prime},\mathcal{W}^{\prime})$_

Algorithm 1 Coreset construction for Robust $(k,z)$-Clustering

###### Proof.

See Algorithm 1 for detailed pseudocode of the coreset algorithm. Now we give
high level idea of the algorithm. Our algorithm is inspired by the grid
construction approach of [14] that yields coresets for $k$-Median and
$k$-Means. Given an instance $\mathcal{I}=(F,P,\mathcal{W})$ of Robust
$(k,z)$-Clustering, the first step is to start with an
$(\alpha,\beta)$-bicriteria solution $B=\\{b_{i}\\}_{i\in[\beta k]}$ that
opens at most $\beta k$ facilities with the guarantee that
$\textsf{cost}_{\mathcal{I}}(B)\leq\alpha\cdot\textsf{OPT}$, for some
constants $\alpha,\beta\geq 1$. Let
$R=\sqrt[z]{\frac{\textsf{cost}_{\mathcal{I}}(B)}{\alpha\tau}}$, where
$\tau:=\max_{{\bf w}\in\mathcal{W}}||{\bf w}||_{1}$. Let
$\Delta=\frac{\max_{p\in P,{\bf w}\in\mathcal{W}}{\bf w}[p]}{\min_{p\in P,{\bf
w}\in\mathcal{W}}{\bf w}[p]}$ be the weight aspect ratio of $\mathcal{I}$.
Then, for each $b_{i}\in B$, consider the balls $\mathcal{B}^{j}_{i}:={\sf
ball}(b_{i},2^{j}R)$, for $j\in\\{0,\cdots,\lceil
2\log(\alpha\Delta)\rceil\\}$. Note that, for ${\bf w}\in\mathcal{W}$, and
$p\in P$ with ${\bf w}[p]>0$, it holds that $\delta(p,B)\leq
R\sqrt[z]{\alpha\tau}$, since
$\delta(p,B)\leq\sqrt[z]{\frac{\textsf{cost}_{\mathcal{I}}(B)}{{\bf
w}[p]}}\leq\sqrt[z]{\frac{\alpha\tau}{{\bf w}[p]}}R\leq
R\sqrt[z]{\alpha\Delta}$. Hence, we have that every point $p\in P$ is
contained in some ball $\mathcal{B}^{j}_{i}$. For $b_{i}\in B$, let
$\mathcal{Q}^{j}_{i}=\mathcal{B}^{j}_{i}-\mathcal{B}^{j-1}_{i}$, for
$j=\\{1,\cdots,\lceil 2\log(\alpha\Delta)\rceil\\}$, be the ring between
$\mathcal{B}^{j}_{i}$ and $\mathcal{B}^{j-1}_{i}$, with
$\mathcal{Q}^{0}_{i}=\mathcal{B}^{0}_{i}$. Decompose every ball
$\mathcal{B}^{j}_{i}$ into smaller balls each of radius
$\frac{\epsilon}{40\alpha}R2^{j}$ using the fact that the metric is a doubling
metric. Since these balls can intersect, assume that every point $p\in P$ lies
in exactly one ball (for example, by associating $p$ to the smallest ball
containing $p$, breaking ties arbitrarily). For every ball
$\mathcal{B}^{j}_{i}$ and every smaller ball $t$ of $\mathcal{B}^{j}_{i}$ with
$|t\cap\mathcal{Q}^{j}_{i}|\neq\emptyset$, pick an arbitrary point
$p^{\prime}\in t\cap\mathcal{Q}^{j}_{i}$ as the _representative_ of (the
points in) $t\cap\mathcal{Q}^{j}_{i}$, and add $p^{\prime}$ to the coreset
$P^{\prime}$ with group weight vectors as follows. For every group vector
${\bf w}\in\mathcal{W}$, create a new group vector ${\bf
w}^{\prime}\in\mathcal{W}^{\prime}$ and set $\eta({\bf w})={\bf w}^{\prime}$.
Then,

${\bf w}^{\prime}[p^{\prime}]:=\sum_{p\in t\cap Q^{j}_{i}}{\bf w}(p),$

Intuitively, $\eta({\bf w})[p^{\prime}]$ captures the total weight of points
of ${\bf w}$ in $t\cap\mathcal{Q}^{j}_{i}$. This concludes the coreset
construction.

The high-level idea above is to decompose each ball $\mathcal{B}^{j}_{i}$ into
smaller balls and pick a distinct point as the representative of points in the
non-empty decomposed ball. Additionally, such representative $p^{\prime}$
participates in the group $\eta({\bf w})$ with weight which is sum of the
weights of points in ${\bf w}$ that are represented by $p^{\prime}$. However,
we want to decompose the ball $\mathcal{B}^{j}_{i}$ into smaller balls in a
way that the total number of balls remains the same, irrespective of the
radius of the ball. This is necessary as for higher values of $j$, this number
would depend on $n$, if we are not careful. While this doesn’t seem to help
much, as the radius of the decomposed balls is much large for higher values
$j$, it actually does the trick: since the points in these balls are far from
$b_{i}$, and hence their connection cost to $b_{i}$ is also large. This allows
us to represent the radii of larger balls in terms of the connection cost of
its points to $B$, thus bounding the error in terms of the cost of $B$, which
in turn is bounded by $\alpha\textsf{OPT}$, which gives us the desired
guarantee.

First, let us bound $|P^{\prime}|$. Note
$|P^{\prime}|=\mathcal{O}(|B|\log(\alpha n)\left(\frac{\alpha
3^{z}}{\epsilon}\right)^{\mathcal{O}\left(d\right)})$, assuming
$\Delta=\textsf{poly}(n,m)$. We will use the following bi-criteria algorithm
for Robust $(k,z)$-Clustering due [18].

######  Theorem 3.2 ( [18]).

There exists a polynomial time algorithm for Robust $(k,z)$-Clustering that,
for every $\gamma\in(0,1)$, outputs at most $\frac{k}{1-\gamma}$ centers whose
cost is bounded by $\frac{e^{O(z)}}{1-\gamma}$ times the optimal cost.

Invoking Algorithm 1 with the above bi-criteria solution for $\gamma=1/2$, we
get
$|P^{\prime}|=\left(\frac{2^{z}}{\epsilon}\right)^{\mathcal{O}\left(d\right)}kz\log
n$, as desired. Note that the running time of the algorithm is
$\left(\frac{2^{z}}{\epsilon}\right)^{\mathcal{O}\left(d\right)}\textsf{poly}(n)$.

We now prove the correctness of the algorithm. Fix $X\subseteq F$ of size $k$.
We want to show that, for any $\epsilon>0$,

$\max_{{\bf w}\in\mathcal{W}}(1-\epsilon)\textsf{cost}({\bf
w},X)\leq\max_{\eta({\bf w})\in\mathcal{W}^{\prime}}\textsf{cost}(\eta({\bf
w}),X)\leq\max_{{\bf w}\in\mathcal{W}}\textsf{cost}({\bf w},X).$

Let ${\bf w}_{X}\in\mathcal{W}$ be the group that maximizes the quantity
$\textsf{cost}({\bf w},X)$. To this end, we show that, for ${\bf
w}\in\mathcal{W}$,

$(1-\epsilon)\textsf{cost}({\bf w},X)\leq\textsf{cost}(\eta({\bf
w}),X)\leq(1+\epsilon)\textsf{cost}({\bf w}_{X},X).$ (1)

Note that this is a weaker guarantee on the upper bound of the cost of ${\bf
w}\in\mathcal{W}$, in the sense that, instead of $\textsf{cost}(\eta({\bf
w}),X)\leq(1+\epsilon)\textsf{cost}({\bf w},X)$, it only guarantees
$\textsf{cost}(\eta({\bf w}),X)\leq(1+\epsilon)\textsf{cost}({\bf w}_{X},X)$.
However, this is sufficient to get the desired result. For $p\in P$, let
$r(p)\in P^{\prime}$ be the representative of $p$. Now, we prove the coreset
guarantee of Equation 1. Using the inequality999This can be proved using
induction on $z$. $|a^{z}-b^{z}|\leq|(a-b)(a+b)^{z-1}|$, for $a,b\geq 0$, we
have that for any ${\bf w}\in\mathcal{W}$, the total error
$\mathcal{E}:=|\textsf{cost}(\eta({\bf w}),X)-\textsf{cost}({\bf w},X)|$ is
bounded by,

$\mathcal{E}\leq\sum_{p\in P}|({\bf w}[p]\delta(p,X)^{z}-{\bf
w}[p]\delta(r(p),X)^{z})|\leq\sum_{p\in P}{\bf
w}[p]|(\delta(p,X)-\delta(r(p),X))(\delta(p,X)+\delta(r(p),X))^{z-1}|$

Note that
$|(\delta(p,X)-\delta(r(p),X))|\leq|(\delta(p,r(p))+\delta(r(p),X)-\delta(r(p),X))|\leq\delta(p,r(p))$.
Further, $\delta(p,X)+\delta(r(p),X)\leq 2\delta(p,X)+\delta(p,r(p))$. Hence,

$\mathcal{E}\leq\sum_{p\in P}{\bf
w}[p]\cdot\delta(p,r(p))(2\delta(p,X)+\delta(p,r(p)))^{z-1}.$

To bound $\mathcal{E}$, we divide the points in $P$ in three parts, and bound
the errors on each part separately. Let $P_{R}:=\\{p\in P\mid\delta(p,B)\leq
R\ \&\ \delta(p,X)\leq R\\}$, $P_{B}:=\\{p\in P\mid\delta(p,B)>R\text{ and
}\delta(p,X)\leq\delta(p,B)\\}$, and $P_{X}:=\\{p\in P\mid\delta(p,X)>R\text{
and }\delta(p,B)\leq\delta(p,X)\\}$.

For $p\in P_{R}$, we have $\delta(p,r(p))\leq\frac{\epsilon R}{\alpha
3^{z+1}}$, and $\delta(p,X)\leq R$, and hence we have,

$\displaystyle\mathcal{E}_{R}$ $\displaystyle\leq\sum_{p\in P_{R}}{\bf
w}[p]\frac{\epsilon R}{\alpha 3^{z+1}}\left(2R+\frac{\epsilon R}{\alpha
3^{z+1}}\right)^{z-1}$ $\displaystyle\leq\frac{\epsilon R^{2}}{\alpha
3^{z+1}}\left(2+\frac{\epsilon}{\alpha 3^{z+1}}\right)^{z-1}\sum_{p\in
P_{R}}{\bf w}[p]$
$\displaystyle\leq\frac{\epsilon\textsf{OPT}}{9\alpha\tau}\sum_{p\in
P_{R}}{\bf w}[p]$
$\displaystyle<\frac{\epsilon}{3}\textsf{OPT}\qquad\text{since }\tau\geq||{\bf
w}||_{1}.$

For $p\in P_{B}$, suppose $2^{j}R\geq\delta(p,B)>2^{j-1}R$, for some $j\geq
1$. Then, note that $\delta(p,r(p))\leq 2\frac{\epsilon 2^{j}R}{\alpha
3^{z+2}}<2\frac{2\epsilon\delta(p,B)}{\alpha 3^{z+2}}<\frac{\epsilon}{\alpha
3^{z}}\delta(p,B)$. Hence, we bound $\mathcal{E}_{B}$ using the fact
$\delta(p,X)\leq\delta(p,B)$,

$\displaystyle\mathcal{E}_{B}$ $\displaystyle\leq\sum_{p\in P_{B}}{\bf
w}[p]\frac{\epsilon}{\alpha
3^{z}}\delta(p,B)^{z}\left(2+\frac{\epsilon}{\alpha
3^{z}}\right)^{z-1}\leq\frac{\epsilon}{3\alpha}\sum_{p\in P_{B}}{\bf
w}[p]\delta(p,B)^{z}\leq\frac{\epsilon}{3}\textsf{OPT}.$

For $p\in P_{X}$, suppose $\delta(p,B)>R$, then
$2^{j}R\geq\delta(p,B)>2^{j-1}R$, for some $j\geq 1$. In this case, we have
$\delta(p,r(p))\leq 2\frac{\epsilon 2^{j}R}{\alpha
3^{z+2}}<2\frac{2\epsilon\delta(p,B)}{\alpha 3^{z+2}}<\frac{\epsilon}{\alpha
3^{z}}\delta(p,B)\leq\frac{\epsilon}{\alpha 3^{z}}\delta(p,X)$. Otherwise,
$\delta(p,B)\leq R$, in which case $\delta(p,r(p))\leq 2\frac{\epsilon
R}{\alpha 3^{z+2}}<\frac{2\epsilon}{\alpha 3^{z+2}}\delta(p,X)$. Hence,

$\displaystyle\mathcal{E}_{X}$ $\displaystyle\leq\sum_{p\in P_{X}}{\bf
w}[p]\frac{\epsilon}{\alpha
3^{z}}\delta(p,X)^{z}\left(2+\frac{\epsilon}{\alpha
3^{z}}\right)^{z-1}\leq\frac{\epsilon}{3\alpha}\sum_{p\in P_{X}}{\bf
w}[p]\delta(p,X)^{z}\leq\frac{\epsilon}{3}\textsf{cost}({\bf w},X).$

Thus, letting $O$ denote the optimal solution for $\mathcal{I}$, and using
$\textsf{OPT}=\textsf{cost}_{\mathcal{I}}(O)\leq\textsf{cost}_{\mathcal{I}}(X)=\textsf{cost}({\bf
w}_{X},X)$, we have,

$\mathcal{E}\leq\frac{\epsilon}{3}\left(2\textsf{cost}({\bf
w}_{X},X)+\textsf{cost}({\bf w},X)\right)\leq\epsilon\textsf{cost}({\bf
w}_{X},X).$

On the other hand, $\textsf{cost}(\eta({\bf w}),X)\geq\textsf{cost}({\bf
w},X)-\epsilon\textsf{cost}({\bf w}_{X},X)\geq(1-\epsilon)\textsf{cost}({\bf
w},X)$. ∎

###  3.2 EPAS for Robust $(k,z)$-Clustering

In this section, we show how to use the coreset obtained from Theorem 3.1 to
obtain a $(1+\epsilon)$-approximate solution to the Robust $(k,z)$-Clustering
problem to obtain EPAS with respect to $k$ and $d$, when $|P|$ is small. By
scaling the distances in the instance of Robust $(k,z)$-Clustering, we assume
that the distances are between $1$ and $\Delta^{\prime}$, for some number
$\Delta^{\prime}$. Our algorithm (see Algorithm 2) uses the leader guessing
idea of [9]. In the leader guessing approach, we guess the leader of every
partition of an (fixed) optimal solution, where the leader of a partition is a
closest point (client) in $P$ to the corresponding optimal center. However,
each point can participate in multiple groups, resulting into total number of
points being dependent on the number of groups, $|\mathcal{W}|$. But, we show
next that guessing the leaders from $P$ without bothering about the groups
$\mathcal{W}$ is in fact sufficient. Further, to get a
$(1+\epsilon)$-approximate solution, we use the ball decomposition lemma, as
shown in Algorithm 2.

######  Theorem 3.3.

For any $\epsilon>0$, Algorithm 2, on input $\mathcal{I}=(F,P,\mathcal{W})$,
computes $X\subseteq F:|X|\leq k$ such that
$\textsf{cost}_{\mathcal{I}}(X)\leq(1+\epsilon)\textsf{OPT}$ in time
$\left((\frac{z}{\epsilon})^{d}\log
n\right)^{\mathcal{O}\left(k\right)}|P|^{k}\textsf{poly}(n,m)$.

###### Proof.

First we bound the runtime of the algorithm. The leader enumeration (first
forall loop) requires at most $|P|^{k}$ loops, one for each $k$-tuple of $P$.
Assuming $\Delta^{\prime}=\textsf{poly}(n)$, the radii enumeration (second
forall loop) for the leaders requires at most $\left(\frac{\nicefrac{{\log
n}}{{\epsilon}}}{\epsilon}\right)^{\mathcal{O}\left(k\right)}=(\log
n/\epsilon)^{\mathcal{O}\left(k\right)}$ loops using discretized steps of size
that is power of $(1+\nicefrac{{\epsilon}}{{10z}})$. Finally, there are at
most $(\frac{z}{\epsilon})^{\mathcal{O}\left(dk\right)}$ many $k$-tuples of
$T_{1}\times\cdots\times T_{k}$ since
$|T_{i}|=(\frac{z}{\epsilon})^{\mathcal{O}\left(d\right)}$, yielding the
claimed runtime.

For correctness, we will show that, for any group ${\bf w}\in\mathcal{W}$, we
have $\textsf{cost}({\bf w},X)\leq(1+\epsilon)\textsf{cost}({\bf w},O)$, which
implies
$\textsf{cost}_{\mathcal{I}}(X)\leq(1+\epsilon)\textsf{cost}_{\mathcal{I}}(O)$,
where $O=\\{o_{1},\cdots,o_{k}\\}$ is an optimal solution center. Let
$\Pi_{i}$ be the set of points in $P$ served by $o_{i}$, for $i\in[k]$. Let
$\ell^{*}_{i}\in\Pi_{i}$ be a point that is closest to $o_{i}$. Let this
distance be $\lambda^{*}_{i}$, i.e.,
$\lambda^{*}_{i}:=\delta(\ell^{*}_{i},o_{k})$. We call $\ell^{*}_{i}$ as the
leader of $\Pi_{i}$ with radius $\lambda^{*}_{i}$. Let $\lambda^{\prime}_{i}$
be the smallest number equal to some power of
$(1+\nicefrac{{\epsilon}}{{10z}})$ that is larger than $\lambda^{*}_{i}$.
Then, note that
$\lambda^{\prime}_{i}\geq\lambda^{*}_{i}\geq\frac{\lambda^{\prime}_{i}}{(1+\epsilon/10z)}$.
Next, consider the $\frac{\epsilon}{20z}$-ball decomposition of ${\sf
ball}(\ell^{*}_{i},\lambda^{\prime}_{i})$, and let $b^{*}_{i}$ be a ball
containing $o_{i}$ and let $t^{*}_{i}$ be its center. Now, consider the
iteration of the algorithm corresponding to leader-radii enumeration
$(\ell^{*}_{1},\cdots,\ell^{*}_{k})$ and
$(\lambda^{\prime}_{1},\cdots,\lambda^{\prime}_{k})$ and, center enumeration
$(t^{*}_{1},\cdots,t^{*}_{k})$. Then, for any $p\in\Pi_{i},i\in[k]$, we have
that

$\delta(p,t^{*}_{i})\leq\delta(p,o_{i})+\delta(o_{i},t^{*}_{i})\leq\delta(p,o_{i})+\frac{\epsilon}{10z}\lambda^{\prime}_{i}\leq\delta(p,o_{i})+\frac{\epsilon}{10z}\left(1+\frac{\epsilon}{10z}\right)\lambda^{*}_{i}\leq\left(1+\frac{\epsilon}{5z}\right)\delta(p,o_{i}).$

Hence, for any group ${\bf w}\in\mathcal{W}$, we have ${\bf
w}[p]\delta(p,t^{*}_{i})^{z}\leq(1+\frac{\epsilon}{5z})^{z}{\bf
w}[p]\delta(p,o_{i})^{z}\leq(1+\epsilon){\bf w}[p]\delta(p,o_{i})^{z}$, where
we used the inequality $(1+\frac{\epsilon}{5z})^{z}\leq e^{\epsilon/5}\leq
1+\frac{\epsilon}{5}+(\frac{\epsilon}{5})^{2}+\cdots\leq 1+\epsilon$. Hence,
$\textsf{cost}({\bf w},X)=\sum_{p\in
P}w[p]\delta(p,X)^{z}\leq(1+\epsilon)\textsf{cost}({\bf w},O)$. ∎

Data: Instance $\mathcal{I}=(F,P,\mathcal{W})$ of Robust $(k,z)$-Clustering

Result: $(1+\epsilon)$-approximate solution $X\subseteq F$

1 Let $X\leftarrow\emptyset$;

2 forall  _$k$ -tuples $(\ell_{1},\cdots,\ell_{k})$ of $P$_ do

3 forall  _$k$ -tuples $(\lambda_{1},\cdots,\lambda_{k})$ radii of
$(\ell_{1},\cdots,\ell_{k})$ that are power of
$(1+\nicefrac{{\epsilon}}{{10z}})$ _ do

4 for  _$i\in[k]$_ do

$\mathcal{B}_{i}\leftarrow\\{\frac{\epsilon}{20z}$-ball decomposition of ${\sf
ball}(\ell_{i},\lambda_{i})$};

// For e.g., use Lemma A.1

5

6 end for

7 $T_{i}\leftarrow\\{f\in F\mid f\text{ is an arbitrary facility in ball
}b\in\mathcal{B}_{i}\\}$ 101010If $F=\mathbb{R}^{d}$ then
$T_{i}\leftarrow\\{x_{b}\in F\mid x_{b}\text{ is the center of ball
}b\in\mathcal{B}_{i}\\}$ ;

8 forall  _$k$ -tuples $(t_{1},\cdots,t_{k})$ of $T_{1}\times\cdots\times
T_{k}$_ do

9 if  _$\textsf{cost}_{\mathcal{I}}(\\{t_{1},\cdots,t_{k}\\})
<\textsf{cost}(,\mathcal{I},X)$_ then

10 $X\leftarrow\\{t_{1},\cdots,t_{k}\\}$

11 end if

12

13 end forall

14

15 end forall

16

17 end forall

return _$X$_

Algorithm 2 $(1+\epsilon)$-approximation algorithm for Robust
$(k,z)$-Clustering

Now we conclude this section by proving the main claim of this section (or in
other words proof of Theorem 1.2) by using the results of Theorem 3.1 and
Theorem 3.3 as follows.

###### Proof of Theorem 1.2.

Given an instance $\mathcal{I}=(F,P,\mathcal{W})$ of Robust
$(k,z)$-Clustering, and the accuracy parameter $\epsilon>0$, we invoke Theorem
3.1 on $\mathcal{I}$ with parameter $\epsilon/10$ to obtain an coreset
$(P^{\prime},\mathcal{W}^{\prime})$ such that $P^{\prime}\subseteq
P:|P^{\prime}|=\left(\frac{2^{z}}{\epsilon}\right)^{\mathcal{O}\left(d\right)}kz\log
n$. Let $\mathcal{I}^{\prime}=(F,P^{\prime},\mathcal{W}^{\prime})$ be the
resulting instance. Then, we invoke Theorem 3.3 on $\mathcal{I}^{\prime}$ with
parameter $\epsilon/10$ to obtain $X\subseteq F:|X|\leq k$ such that
$\textsf{cost}_{\mathcal{I}^{\prime}}(X)\leq(1+\epsilon/10)\textsf{OPT}(\mathcal{I}^{\prime})$.

First we analyze the overall running time. With
$|P^{\prime}|=\left(\frac{2^{z}}{\epsilon}\right)^{\mathcal{O}\left(d\right)}kz\log
n$, Theorem 3.3 runs in time
$\left(\left(\frac{2^{z}}{\epsilon}\right)^{d}kz\log
n\right)^{\mathcal{O}\left(k\right)}\textsf{poly}(n,m)$, leading to
$\left(\left(\frac{2^{z}}{\epsilon}\right)^{d}zk\log
k\right)^{\mathcal{O}\left(k\right)}\textsf{poly}(n,m)$ as the overall running
time as desired. For the correctness, let $F^{\prime*}$ be an optimal solution
for $\mathcal{I}^{\prime}$. Then,

$\displaystyle\textsf{cost}_{\mathcal{I}}(X)$
$\displaystyle\leq(1+\epsilon/10)\textsf{cost}(\mathcal{I}^{\prime},X)$
$\displaystyle\leq(1+\epsilon/10)^{2}\textsf{cost}(\mathcal{I}^{\prime},F^{\prime*})$
$\displaystyle\leq(1+\epsilon/10)^{2}(1+2\epsilon/10)\textsf{cost}_{\mathcal{I}}(F^{\prime*})$
$\displaystyle\leq(1+\epsilon)\textsf{OPT}(\mathcal{I}).$

∎

##  4 High-Dimensional Discrete Euclidean Space

###  4.1 Hardness of Discrete $k$-Center

For this section, we use the following explicit construction of the so-called
_$\eta$ -balanced error-correcting codes_ from a recent result of Ta-Shma [19]
which we rephrase for our purposes as follows:

######  Theorem 4.1.

Let $\eta\in(0,1/2)$ be a positive constant. Then there is an algorithm that
computes, for any given number $s\in\mathbb{N}$, an $s$-element set
$B\subseteq\\{0,1\\}^{t}$ of binary vectors of dimension $t=\mathcal{O}(\log
s/\eta^{2+o(1)})$ such that for any $b\in B$, its Hamming weight $||b||_{1}$
and for any $b^{\prime}\in B\setminus\\{b\\}$, the Hamming distance
$||b-b^{\prime}||_{1}$ both lie in the interval $[(1/2-\eta)t,(1/2+\eta)t]$.
The running time of the algorithm is $\mathcal{O}(st)$.

###### Proof.

Ta-Shma [19] gives an explicit construction of a
$t\times\lceil\log_{2}s\rceil$ binary matrix generating a linear, binary,
error-correcting code of message length $\lceil\log_{2}s\rceil$, block length
$t=\mathcal{O}(\log s/\eta^{2+o(1)})$, and pairwise Hamming distance between
$(1/2-\eta)t$ and $(1/2+\eta)t$. Since the code is linear, it contains the
zero code word. Hence each code word has Hamming weight in
$[(1/2-\eta)t,(1/2+\eta)t]$. The time for constructing the matrix is
polynomial in $\log s$ and $t$. Using the generating matrix, at least $s$ many
non-zero code words can be enumerated in time $\mathcal{O}(st)$, which
dominates the time for computing the matrix.

∎

For a binary vector $p$, denote by $\bar{p}$ the binary vector obtained from
$p$ by flipping each coordinate. Use this theorem to construct a set $P$ of
$n$ binary data points in dimension $t=\mathcal{O}(\log n/\eta^{2+o(1)})$ and
let $F=\\{\,\bar{p}\mid p\in P\,\\}$. Now consider any sequence
$p_{1},x_{1},\dots,p_{n-1},x_{n-1}$ of points and centers in $P$ and $F$,
respectively, such that $p_{1}\in P$ is arbitrary, $x_{i}\in
F\setminus\\{\bar{p}_{1},\dots,\bar{p}_{i}\\}$ is arbitrary, and
$p_{i}=\bar{x}_{i-1}$ for $i\in[n-1]$. Then
$||x_{i}-p_{j}||_{1}\leq(1/2+\eta)t$ for all $j<i\leq n-1$ and
$||p_{i}-x_{i}||_{1}\geq(1-2\eta)t$ for all $i\in[n-1]$.

This example can be used as a gadget in a hardness proof for discrete
$k$-Center.

See 1.1

###### Proof.

We show a reduction from Multi-Colored Independent Set, which is known to be
$W[1]$-hard [10]. The input is a $k$-partite graph $G=(V,E)$ with
$k$-partition $V_{1},\dots,V_{k}$. The question is if there is an independent
set that is _multi-colored_ , that is, it has precisely one node from each set
$V_{i}$, $i\in[k]$. W.l.o.g. we assume that each $V_{i}$ contains at least one
node that is adjacent to all nodes $V\setminus V_{i}$. Adding such nodes, we
can moreover assume that $|V_{i}|=n/k$ for each $i\in[k]$ where $n=|V|$.

Fix some constant $\eta\in(0,1/2)$. Using Theorem 4.1, we construct a set
$B\subseteq\\{0,1\\}^{t}$ of $n$ nearly equidistant code words of dimension
$t=\mathcal{O}(\log n/\eta^{2+o(1)})$. We map each node $u\in V$ uniquely to
some non-zero code word $b(u)\in B$. We construct a $k$-Center instance in
$\mathbb{R}^{k\cdot t}$ as follows. We subdivide the coordinates of each point
in $\mathbb{R}^{k\cdot t}$ into $k$ _blocks_ each containing $t$ consecutive
coordinates. Our set $P$ of data points contains for each node $v_{i}\in
V_{i}$, $i\in[k]$ the point $p(v_{i})\in P$ in which the $i$th block equals
$b(v_{i})$ and all other coordinates are zero. For each edge $(v_{i},v_{j})$
for distinct $i,j\in[k]$ we create a point $p(v_{i},v_{j})\in P$ in which the
$i$th block equals $\bar{b}(v_{i})$, the $j$th block equals $\bar{b}(v_{j})$,
and all other coordinates are zero. This completes the construction of the
data point set $P$. The number of centers is chosen to be $k$ completing the
construction of the $k$-Center instance.

We have that $||p(v_{i})-p(v_{i}^{\prime})||_{q}^{q}\leq(1/2+\eta)t$ and
$||p(v_{i}^{\prime})-p(v_{i},v_{j})||_{q}^{q}\leq(1+2\eta)t$ for any distinct
triplet $v_{i},v_{i}^{\prime},v_{j}\in V_{i}$ and $(v_{i},v_{j})\in E$. Hence
if there is a multi-colored independent set $I$ for $G$ then $X=\\{\,p(u)\mid
u\in I\,\\}$ is a $k$-element set such that $\delta(p,X)^{q}\leq(1+2\eta)t$
for any $p\in P$ under the $\ell_{q}$ metric.

Now assume that there is no multi-colored independent set for $G$. Consider an
arbitrary $k$-element set $X\subseteq V$. We say that $x\in X$ _covers_ $p\in
P$ if $\delta(p,x)^{q}<(3/2-3\eta)t$. We claim that there is some $p\in P$ not
covered by any center in $X$. The correctness of this claim implies that any
parameterized approximation algorithm with approximation ratio strictly better
than $((3/2-3\eta)/(1+2\eta))^{1/q}$ implies that $W[1]=FPT$ and thus the
theorem.

In order to prove this claim, we assume for the sake of contradiction, that
all $p\in P$ are covered by some center in $X$. We claim that w.l.o.g. $X$
contains no point of the form $p(v_{i},v_{j})$ where $(v_{i},v_{j})\in E$. We
have that $||p(v_{i},v_{j})-p(v_{g}^{\prime})||_{q}^{q}\geq(3/2-3\eta)t$ if
$g\notin\\{i,j\\}$. Hence $p(v_{i},v_{j})$ can cover $p(v_{g}^{\prime})$ only
if $g=i$ or $g=j$. Similarly, $p(v_{i},v_{j})$ can cover
$p(v_{g}^{\prime},v_{h}^{\prime})$ only if $i=g$ and $j=h$. But then these
points would be covered by $p(v_{i})$ as well and hence we could replace
$p(v_{i},v_{j})$ with $p(v_{i})$. We therefore assume that $X$ contains only
points of the form $p(v_{i})$.

We claim that $X$ is multi-colored. Otherwise, there would be some $V_{i}$
that contains no point from $X$. By our initial assumption, $V_{i}$ contains
some point $v_{i}$ that is adjacent to all points $V\setminus V_{i}$. Assuming
$k\geq 3$ there exists at least one $V_{j}$, $j\neq i$ that contains at most
one node from $X$. If $V_{j}$ contains a node in $X$, then let $v_{j}\in
V_{j}\cap X$ , and otherwise let $v_{j}$ be an arbitrary node in $V_{j}$. By
our assumption $(v_{i},v_{j})\in E$. If $v_{j}\in X$ then
$||p(v_{j})-p(v_{j},v_{i})||_{q}^{q}\geq(3/2-\eta)t$ because the $j$th block
of $p(v_{j})$ equals $b(v_{j})$ and the $i$th block of $p(v_{j},v_{i})$ equals
$\bar{b}(v_{j})$. If $v_{j}\notin X$ then for any $v_{h}\in X$ we have
$h\notin\\{i,j\\}$. Thus
$||p(v_{h})-p(v_{i},v_{j})||_{q}^{q}\geq(3/2-3\eta)t$. Hence $p(v_{i},v_{j})$
would not be covered showing that $X$ is multi-colored. Since $X$ is multi-
colored it can not be an independent set. Hence there exists some edge
$(v_{i},v_{j})$ such that $v_{i},v_{j}\in X$ but then
$||p(v_{i})-p(v_{i},v_{j})||_{q}^{q}\geq(3/2-\eta)t$,
$||p(v_{j})-p(v_{i},v_{j})||_{q}^{q}\geq(3/2-\eta)t$,
$||p(v_{h})-p(v_{i},v_{j})||_{q}^{q}\geq(3/2-3\eta)t$ and hence
$\delta(p(v_{i},v_{j}),X)\geq(3/2-3\eta)t$, implying that $p(v_{i},v_{j})$ is
not covered. ∎

###  4.2 FPT Approximation Algorithm for Robust $(k,z)$-Clustering

In this section, we exploit the Euclidean properties of the metric to show the
following result that breaches the barrier of $3^{z}$-approximation for Robust
$(k,z)$-Clustering in general metrics.

See 1.3

This is in contrast to the $3^{z}$-approximation of [13] for general metrics,
which relies on the following Lemma 4.1. Further note that the running time of
Theorem 1.3 is comparable with the running time of the result of Goyal and
Jaiswal (Ref. Corollary 3 of [13]).

######  Lemma 4.1.

Let $(Y,\delta)$ be a metric space, and $B\subseteq Y$. Then for any set
$X\subseteq Y$, there exists an assignment $\sigma\colon X\rightarrow B$ such
that, for all $x\in X$, we have $\delta(x,\sigma(X))\leq
2\delta(x,X)+\delta(x,B)$.

###### Proof.

For each $x\in F$, define $\sigma(i)$ as $\pi_{B}(x)$, the point in $B$
closest in distance to $x$. Notice that for any $x,y$, we have
$\delta(y,\pi(x))\leq\delta(y,x)+\delta(x,\sigma(x))$ where
$\delta(x,\sigma(x))=\delta(x,B)\leq\delta(x,y)+\delta(y,B)$. ∎

Note that this lemma itself is tight even in $1$-dimensional Euclidean
space(see Figure 1).

$b$$o$$p$$b^{\prime}$ Figure 1: Here is an example showing that the algorithm
of Goyal and Jaiswal [13] is tight even for line metric. Suppose $o\in O$ is
an optimum facility that serves client $p$, and $b^{\prime}\in B$ is a
facility that serves client $p$ in $B$. Suppose by our assignment rule we have
$\sigma(o)=b$. We assume, w.l.o.g, that $o$ is at the origin of the coordinate
system and that $b=(-1,0)$. Now suppose client $p$ is within distance
$\frac{1}{2}$ from $o$ and $b^{\prime}$, i.e., $p=(\frac{1}{2},0)$, and
$b^{\prime}=(1,0)$. In this example the cost for optimum solution is
$\frac{1}{2}$, the cost for a solution $B$ is $\frac{1}{2}$ and the cost for
the algorithm is $\frac{3}{2}$, hence it shows that the algorithm is tight for
the ratio and also for the connection costs.

In order to get around this issue, we make use of the property of our
geometric space. For any subset $B\subseteq\mathbb{R}^{d}$, define the mid-
point closure of $B$ as ${\sf
cl}(B)=B\cup\\{\pi_{F}\left(\frac{b+b^{\prime}}{2}\right):b,b^{\prime}\in
B\\}$. Notice that the size $|{\sf cl}(B)|=O(|B|^{2})$. For $\beta>0$ and sets
$O,B\subseteq\mathbb{R}^{d}$, we say that point $p\in P$ is $\beta$-far (from
$O$ w.r.t. $B$) if $\delta(p,O)\geq\beta\cdot\delta(p,B)$. Our main technical
contribution is encapsulated below.

######  Lemma 4.2 (Assignment Lemma).

Let $\beta_{0}=0.05$ and let $B\subseteq{\mathbb{R}}^{d}$. Then, for any
$O\subseteq{\mathbb{R}}^{d}$, there exists an assignment $\sigma\colon
O\rightarrow{\sf cl}(B)$ such that, for all $\beta_{0}$-far points
$p\in{\mathbb{R}}^{d}$, we have
$\delta(p,\sigma(O))\leq(1-\epsilon_{0})(2\delta(p,O)+\delta(p,B))$ where
$\epsilon_{0}>0.002$.

To prove Lemma 4.2, we first need to define our assignment function $\sigma$.
For $O,B\subseteq\mathbb{R}^{d}$, consider an arbitrary point $o\in O$, and
let $b=\pi_{B}(o)$. Define $\sigma(o)=b$ if ${{\sf ball}(q,\alpha)\cap
B=\varnothing}$, and define $\sigma(o)=\pi_{\sf cl(B)}(o)$ otherwise. Here,
$q$ is the mirror image of $b$ w.r.t. $o$ (See Figure 2).

Let $O$ be a feasible solution of a given instance and consider a client $p$.
Our objective in this section is to analyze the displacement $p$ incurs under
the assignment rule $\sigma$. Recall from Lemma 4.1 that if the assignment
rule is defined as $\sigma(o)=\pi_{B}(o)$, client $p$ would incur
$2||p-o||+||p-b^{\prime}||$ cost assuming it is served by $o$ and $b^{\prime}$
in $O$ and $B$, respectively. We therefore, tend to analyze the displacement
ratio defined as follows:

######  Definition 4.1.

For a given small constant $\beta>0$, let the displacement ratio be defined as

$\gamma_{\beta}=\max_{\begin{subarray}{c}o\in O,b^{\prime}\in B\\\
p\in\mathbb{R}^{d}\backslash{\sf
ball}(o,\beta),\end{subarray}}\left\\{\frac{||p-\sigma(o)||}{2||p-o||+||p-b^{\prime}||}\right\\}$

With defining $\gamma$, we aim to find the potential locations for a client
$p$ and $b^{\prime}\in B$ that maximize the ratio of the cost $p$ in the
solution $\sigma(O)$ to its default maximum cost obtain via Lemma 4.1. We show
that the parameter $\gamma_{\beta}$ can be upper-bounded by $1-f(\alpha)$ for
some $\alpha>0$, where $f(\cdot)$ is a function that depends on $\alpha$ and
the geometry of $O$ and $B$. The value of $\alpha$ is such that $B$ intersects
with the $\alpha$-ball around a certain point $q$ in $\mathbb{R}^{d}$.

Overall, Lemma 4.2 is proved by showing that a sufficiently small
$\beta_{0}\leq 0.05$ exists such that $\gamma_{\beta_{0}}\leq
1-\epsilon_{0}\leq 0.9978$. Note that while we assume $O$ to be the optimum
set of centers for the instance, our analysis applies to any feasible solution
$O$.

We are now prepared to prove Lemma 4.2. As previously stated, our objective is
to demonstrate that the parameter $\gamma_{\beta}$ is both upper-bounded and
bounded away from $1$ by a constant for sufficiently small values of $\beta$.

To accomplish this, we make use of the following claim:

######  Claim 4.2.1.

Following the assignment rule $\sigma$, we have that $\gamma_{\beta}\leq
1-f(\alpha,\beta)$.

For the sake of notation, we drop the subscript of $\gamma_{\beta}$ everywhere
in the proof.

###### Proof.

Given $O$ and $B$, we consider a facility $o\in O$. Assume $b\in B$ is a
closest facility to $o$, and $b^{\prime}\in B$ is the bicerteria solution that
serves client $p$. For the sake of presentation, we assume, w.l.o.g., that the
instance is scaled and rotated so that $o$ is at the center of the coordinate
system, $b=(-1,0)$, and $q=(0,1)$ is the mirror image of $b$111111Note that
rotation does not change the distances. Also, since we are interested in the
ratio of some distances in $\mathbb{R}^{d}$, scaling does not affect
$\gamma_{\beta}$.. Now consider the alpha-ball around $q$ and beta-ball around
$o$, for the ease of analyse we consider half plane above $x$-coordinate the
same arguments are hold for half plane below $x$-coordinate. We divide our
analysis into the following cases:

#### Case 1: ${\sf ball}(q,\alpha)\cap B\neq\varnothing$.

Let $b^{\prime}\in{\sf ball}(q,\alpha)\cap B$, it is clear that
$b^{\prime}\in({\sf ball}(q,\alpha)\backslash{\sf ball}(o,1))$. We assign $o$
to the closest facility to the midpoint of $b$ and $b^{\prime}$ i.e
$\sigma(o)=\pi_{F}(\frac{b+b^{\prime}}{2})$, the point $o\in F$ certifies that
$\pi_{F}((b+b^{\prime})/2)$ has distance at most $\alpha$ to $o$ because
$||\pi_{F}((b+b^{\prime})/2)-(b+b^{\prime})/2||\leq||(b+b^{\prime})/2-o||$.
Hence we obtain $||\sigma(o)-o||\leq\alpha$, therefore
$||p-\sigma(o)||\leq||p-o||+\alpha$ (see Figure 2). Recall that the aim is to
upper bound the displacement ratio 4.1 for client $p$, notice that
$||p-o||+||p-b^{\prime}||\geq 1$, we obtain:

$\begin{split}\gamma=\frac{||\sigma(o)-p||}{2||p-o||+||p-b^{\prime}||}&\leq\frac{||p-o||+\alpha}{||p-o||+1}\\\
&\leq 1-\frac{1-\alpha}{||p-o||+1}\\\ &\leq 1-\frac{1-\alpha}{2}\end{split}$

$o$$b^{\prime}$$\leq\frac{\alpha}{2}$$\pi_{F}(\frac{b+b^{\prime}}{2})$$q$$\alpha$$b$

Figure 2: The midpoint of $b$ and $b^{\prime}$ is shown by red dot,
$||(b+b^{\prime})/2-o||\leq\frac{\alpha}{2}$ and $||\sigma(o)-o||\leq\alpha$

.

#### Case 2: ${\sf ball}(q,\alpha)\cap B=\varnothing$.

At first, we split the space into the four regions $R_{1}$, $R_{2}$, $R_{3}$,
and $R_{4}$. Consider $q_{1}$ and $q_{2}$ points of intersection ${\sf
ball}(o,1)$ and ${\sf ball}(q,\alpha)$. Let $q_{3}$ midpoint of $q$ and
$q_{1}$, consider the region $H$ above lines $(q_{3},o)$ and $(o,b)$, we
define $R_{1}=H\backslash{\sf ball}(o,\beta)$. Next, consider $(1-\omega)$ and
$(1+\omega)$ balls around $o$ and let $H^{\prime}$ be the region below the
line $(o,q_{3})$ and above line $(o,q)$, we define $R_{2}=({\sf
ball}(o,1-\omega)\backslash Ball(o,\beta))\cap H^{\prime}$, $R_{3}=({\sf
ball}(o,1+\omega)\backslash Ball(o,1-\omega))\cap H^{\prime})$ and
$R_{4}=H^{\prime}\backslash Ball(o,1+\omega)$ (see figure 3). Now consider the
following cases:

  * •

$p\in R_{1}$, we observe that the best location for $b^{\prime}$ is when it
lies on the point $q_{1}$, let us define $b^{\prime\prime}$ the closest point
to $p$ that is not in the interior set ${\sf ball}(o,1)$ and $p^{\prime}$ a
point on the boundary of $Ball(o,\beta)$ in region $R_{1}$, let us define a
point $p^{\prime\prime}={\sf
ball}(o,\beta)\cap(o,q_{3})=(\beta\cos{\theta},\beta\sin{\theta})$ so that
$\theta$ is $\angle q_{3}oq_{1}$, notice that
$\cos{\theta}=1-\frac{\alpha^{2}}{4}$.

######  Observation 4.1.

For any $\epsilon_{1},\epsilon_{2},X,Y\geq 0$ :

$\frac{X-\epsilon_{1}+Y}{X+Y}\leq\frac{X-\epsilon_{1}+Y+\epsilon_{2}}{X+Y+\epsilon_{2}}$

Consider assigning $p$ to $p^{\prime}$ and $b^{\prime}$ we can bound the
displacement cost as follows:

$\begin{split}\gamma=\frac{||\sigma(o)-p||}{2||p-o||+||p-b^{\prime}||}&\leq\frac{||b-p^{\prime}||+||p-p^{\prime}||}{2||p^{\prime}-o||+||p^{\prime}-b^{\prime\prime}||+||p-p^{\prime}||}\\\
&\leq\frac{||b-p^{\prime\prime}||+||p-p^{\prime}||}{2\beta+1-\beta+||p-p^{\prime}||}\\\
&\leq\frac{\sqrt{(\beta\cos(\theta)+1)^{2}+(\beta\sin(\theta))^{2}}+||p-p^{\prime}||}{1+\beta+||p-p^{\prime}||}\\\
&=\frac{\sqrt{\beta^{2}+2\beta\cos{\theta}+1}+||p-p^{\prime}||}{1+\beta+||p-p^{\prime}||}\\\
&=\frac{\sqrt{(1+\beta)^{2}-\frac{\beta\alpha^{2}}{2}}+||p-p^{\prime}||}{1+\beta+||p-p^{\prime}||}\\\
\end{split}$

Based on observation 4.1 we can bound $||p-p^{\prime}||\leq 1+\beta$ and still
have a valid constraint, therefore:

$\begin{split}\gamma&\leq\frac{(1+\beta)(1+\sqrt{(1-\frac{\beta\alpha^{2}}{2}})}{2(1+\beta)}\\\
&\leq\frac{1}{2}+\frac{\sqrt{1^{2}-\frac{2\beta\alpha^{2}}{4}+\frac{\beta^{2}\alpha^{4}}{16}}}{2}\\\
&\leq\frac{1}{2}+\frac{1-\frac{\beta\alpha^{2}}{4}}{2}\\\
&=1-\frac{4+\beta\alpha^{2}}{8}\end{split}$

  * •

$p\in R_{2}$, we obtain the best location for $b^{\prime}$ is when it lies on
the point $q_{1}$, the cost of displacement is as follows:

$\begin{split}\gamma=\frac{||\sigma(o)-p||}{2||p-o||+||p-b^{\prime}||}&\leq\frac{||p-o||+1}{||p-o||+||p^{\prime}-o||+||p^{\prime}-p||+||p-b^{\prime}||}\\\
&\leq\frac{||p-o||+1}{||p-o||+||p^{\prime\prime}-o||+||p^{\prime\prime}-b^{\prime}||}.\end{split}$

To calculate $||p^{\prime\prime}-b^{\prime}||$ we can consider rotated
$p^{\prime\prime}$ and $b^{\prime}$ so that $p^{\prime\prime}=(\beta,0)$ and
$b^{\prime}=(\cos\theta,\sin\theta)$, then:

$\gamma\leq\frac{||p-o||+1}{||p-o||+\beta+\sqrt{(\cos(\theta)-\beta)^{2}+(\sin(\theta))^{2}}}$

Assume $\beta\leq\frac{\alpha}{12}$ then we have $||p-o||\leq 1-\beta$, hence:

$\begin{split}\gamma&\leq\frac{2-\beta}{1+\sqrt{\beta^{2}-2\beta(1-\frac{\alpha^{2}}{4})+1}}\\\
&\leq\frac{2-\beta}{1+(1-\beta)\sqrt{1+2\beta\frac{\alpha^{2}}{4}}}\\\
&=1-\frac{\sqrt{1+\beta\frac{\alpha^{2}}{2}}(1-\beta)-(1-\beta)}{1+(1-\beta)\sqrt{1+\beta\frac{\alpha^{2}}{2}}}\end{split}$

$o$$q_{1}$$\beta$$q$$\alpha$$b$$p$ (a) $p\in R_{1}$

$b$$\beta$$o$$q_{1}$$q_{3}$$p^{\prime\prime}$$q$$\alpha$$p$ (b) $p\in R_{2}$

$o$$q$$q_{1}$$q_{3}$ (c) $p\in R_{3}$

$b$$\beta$$o$$p$$q_{3}$$q$$\alpha$ (d) $p\in R_{4}$

Figure 3: $o\in O$ is an optimum solution, $b\in B$ is the closest bicriteria
solution to $o$, $1$-ball around $o$ is shown as a dashed circle, alpha-ball
around $q$ and beta-ball around $o$ are shown in blue, $(1-\omega)$ and
$(1+\omega)$ around $o$ are shown as blue dashed circles. The regions are
specified by green borders.

  * •

$p\in R_{3}$, we claim the distance from $p$ to the closest bicriteria
solution $b^{\prime}$ can be bounded as
$||p-b^{\prime}||\geq\frac{\alpha}{3}$.

Suppose $\alpha\leq\frac{6}{10}$, we define
$z=1-||q_{3}-o||\leq\frac{\alpha}{12}$, consider $p^{\prime\prime\prime}$ the
closest point to $p$ on the line $(q_{3},q)$, hence
$||p-p^{\prime\prime\prime}||\leq\frac{\alpha}{6}$, now we have
$\frac{\alpha}{2}\leq||p^{\prime\prime\prime}-b^{\prime}||\leq||p^{\prime\prime\prime}-p||+||p-b^{\prime}||$
, then we obtain $||p-b^{\prime}||\geq\frac{\alpha}{3}$.

$\begin{split}\gamma=\frac{||\sigma(o)-p||}{2||p-o||+||p-b^{\prime}||}&=\frac{||p-o||+1}{||p-o||+(1-\frac{\alpha}{12})+\frac{\alpha}{3}}\\\
&=\frac{||p-o||+1}{||p-o||+1+\frac{\alpha}{4}}\\\
&\leq\frac{2}{2+\frac{\alpha}{4}}\\\ &=1-\frac{\alpha}{8+\alpha}\end{split}$

  * •

$p\in R_{4}$, assume $p$ and $b^{\prime}$ are in the same location, therefore:

$\gamma=\frac{||\sigma(o)-p||}{2||p-o||+||p-b^{\prime}||}\leq
1-\frac{||p-o||-||b-o||}{2||p-o||}$

Notice that $||p-o||\geq 1+\frac{\alpha}{12}$, consider two cases either
$||p-o||\leq 1+\alpha$ or $||p-o||>1+\alpha$:

    * –

$||p-o||\leq 1+\alpha$

$\gamma\leq
1-\frac{{1+\frac{\alpha}{12}}-1}{2(1+\alpha)}=1-\frac{\alpha}{24(1+\alpha)}$

    * –

$||p-o||>1+\alpha$

$\begin{split}\gamma\leq
1-\frac{||p-o||-1}{2||p-o||}&\leq\frac{1}{2}+\frac{1}{2(1+\alpha)}\\\
&=1-\frac{1+\alpha}{2(1+\alpha)}\end{split}$

For all cases, the aim is to optimize $\gamma$ for small constant $\beta$ and
$\alpha$. In the worse case for $\gamma$ we get $\alpha=0.6$, $\beta_{0}=0.05$
and $\gamma=1-0.0022=0.9978$. ∎

In the proof of Theorem 1.3, we first invoke Lemma 4.2 with $O$ being the
optimal solution and $B$ being a
$(1+\epsilon,(k\ln^{2}n)/\epsilon^{2})$-bicriteria approximation of the
problem, say by using the algorithm of Goyal and Jaiswal [13]. Since the
assignment $\sigma$ maps every center in $O$ uniquely to a center in ${\sf
cl}(B)$, then $\sigma(O)$ is a feasible solution of cost $3^{z}-\beta_{0}$
Once we know a subset of ${\sf cl}(B)$ exists with the desired approximation
factor, we can find it in FPT time by enumeration. We show that this new
assignment property is enough to derive an improved FPT approximation for
Robust $(k,z)$-Clustering in Euclidean space.

###### Proof of Theorem 1.3.

Let $B\subseteq{\mathbb{R}}^{d}$ denote a $(1+\epsilon_{0},k\cdot\ln
n^{2}/\epsilon_{0}^{2})$ bi-criteria solution by applying the algorithm of
[13]. We denote the total cost of the set of $\beta_{0}$-near
($\beta_{0}$-far) points by in a bi-criteria solution, an optimum solution,
and the solution returned by our algorithm, respectively. Note that from the
definition of $\beta_{0}$-near points and the (clustering) cost, we have that
$\textsf{OPT}_{\textnormal{n}}\leq\beta_{0}\cdot\textsf{BIC}_{\textnormal{n}}\leq\beta_{0}\cdot\textsf{OPT}$.
Consequently, for the set of $\beta_{0}$-far points, we get
$\textsf{OPT}_{\textnormal{f}}\geq(1-\beta_{0})\cdot\textsf{OPT}$.

For the set of $\beta_{0}$-near points, the best bound on the cost that our
algorithm can achieve is that of Lemma 4.1. Therefore, we get
$\textsf{ALG}_{\textnormal{n}}\leq(2\textsf{OPT}_{\textnormal{n}}+\textsf{BIC}_{\textnormal{n}})$.
On the other hand, by Lemma 4.2, we do save some cost on the $\beta_{0}$-far
points as we have
$\textsf{ALG}_{\textnormal{f}}\leq\big{(}(1-\epsilon_{0})(2\textsf{OPT}_{\textnormal{f}}+\textsf{BIC}_{\textnormal{f}})\big{)}$.
Moreover
$\textsf{BIC}_{\textnormal{n}}+\textsf{BIC}_{\textnormal{f}}=\textsf{BIC}\leq(1+\epsilon_{0})\textsf{OPT}$
by the choice of the bicriteria solution. Putting these factors together, we
obtain

$\displaystyle\textsf{ALG}_{\textnormal{n}}+\textsf{ALG}_{\textnormal{f}}$
$\displaystyle\leq
3^{z-1}\cdot\big{[}(2\textsf{OPT}_{\textnormal{n}}+\textsf{BIC}_{\textnormal{n}})+(1-\epsilon_{0})^{z}(2\textsf{OPT}_{\textnormal{f}}+\textsf{BIC}_{\textnormal{f}})\big{]}$
$\displaystyle\leq
3^{z-1}\cdot\big{[}2\beta_{0}^{z}\textsf{OPT}+2(1-\epsilon_{0})^{z}(1-\beta_{0}^{z})\textsf{OPT}+\textsf{BIC}_{\textnormal{n}}+(1-\epsilon_{0})^{z}\textsf{BIC}_{\textnormal{f}}\big{]}$
$\displaystyle\leq
3^{z-1}\cdot\big{[}2\beta_{0}^{z}\textsf{OPT}+2(1-\epsilon_{0})^{z}(1-\beta_{0}^{z})\textsf{OPT}+\textsf{BIC}_{\textnormal{n}}+\textsf{BIC}_{\textnormal{f}}\big{]}$
$\displaystyle\leq
3^{z-1}\cdot\big{[}2\big{(}\beta_{0}^{z}+(1-\epsilon_{0})^{z}(1-\beta_{0}^{z})\big{)}\textsf{OPT}+(1+\epsilon_{0})\textsf{OPT}\big{]}$
$\displaystyle\leq
3^{z-1}\cdot\big{[}\big{(}2\beta_{0}^{z}+2(1-\epsilon_{0})^{z}-2(1-\epsilon_{0})^{z}\beta_{0}^{z}+1+\epsilon_{0}\big{)}\textsf{OPT}\big{]}$
$\displaystyle\leq
3^{z-1}\cdot\big{[}\big{(}2(1-\epsilon_{0})^{z}+2\beta_{0}^{z}\epsilon_{0}z+1+\epsilon_{0}\big{)}\textsf{OPT}\big{]}\
\ \ \ \ \ \text{(using Bernoulli's inequality)}$ $\displaystyle\leq
3^{z-1}\cdot\big{[}\big{(}2(1-\epsilon_{0})^{z}+(2\beta_{0}^{z}z+1)\epsilon_{0}+1\big{)}\textsf{OPT}\big{]}$
$\displaystyle\leq 3^{z-1}\cdot(3-\epsilon)\textsf{OPT}\ ;\ \epsilon>0.0018\ \
\ \text{(using Claim \ref{claim:kzs})}$
$\displaystyle\leq(3^{z}-\eta_{0})\textsf{OPT}\ ;\ \eta_{0}=\epsilon 3^{z-1}$

where in the first inequality, we used the approximate triangle inequality
$(a+b+c)^{z}\leq 3^{z-1}\cdot(a^{z}+b^{z}+c^{z})$ and in the second
inequality, we use the fact that $OPT_{n}+OPT_{f}=\textsf{OPT}$ and thus, the
maximizer for $2OPT_{n}+2(1-\epsilon_{0})^{z}OPT_{f}$ occurs at the maximum of
$OPT_{n}$.

######  Claim 4.2.2.

For any integer $z$, we have that
$2(1-\epsilon_{0})^{z}+\epsilon_{0}(1+2\beta_{0}^{z}z)\leq 1.9982$

###### Proof.

Let $2(1-\epsilon_{0})^{z}+\epsilon_{0}(1+2\beta_{0}^{z}z)\leq 2-\epsilon$.
Note that, since from Lemma 4.1 we have that $\beta_{0}=0.05$ and
$\epsilon_{0}>0.002$, we get lower bound for $\epsilon$ as follows (the left-
hand side is maximized at $z=1$):
$\epsilon>2-2(1-\epsilon_{0})-\epsilon_{0}(1+2\beta_{0})>0.0018$. ∎

Note that by using the algorithm of [13], the running time of algorithm is
$(k/\epsilon)^{\mathcal{O}\left(k\right)}.n^{\mathcal{O}\left(1\right)}$,
where $\epsilon=\frac{\eta_{0}}{3^{z-1}}$. Hence for $\eta_{0}>0.0006$ and
constant $z$ we get
$(k/\epsilon)^{\mathcal{O}\left(k\right)}.n^{\mathcal{O}\left(1\right)}$ which
is FPT in $k$. ∎

## Acknowledgements

Fateme Abbasi, Sandip Banerjee and Jarosław Byrka are supported by Polish
National Science Centre (NCN) Grant 2020/39/B/ST6/01641. Parinya Chalermsook
is supported by European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (grant agreement No 759557).
Dániel Marx is supported by the European Research Council (ERC) consolidator
grant No. 725978 SYSTEMATICGRAPH.

## References

  * [1] Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase.  Parameterized approximation schemes for clustering with general norm objectives.  CoRR, abs/2304.03146, 2023.
  * [2] Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian.  Fair clustering via equitable group representations.  In Madeleine Clare Elish, William Isaac, and Richard S. Zemel, editors, FAccT ’21: 2021 ACM Conference on Fairness, Accountability, and Transparency, Virtual Event / Toronto, Canada, March 3-10, 2021, pages 504–514. ACM, 2021.
  * [3] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward.  Better guarantees for k-means and euclidean k-median by primal-dual algorithms.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 61–72. IEEE Computer Society, 2017.
  * [4] Barbara M. Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan.  A plant location guide for the unsure: Approximation algorithms for min-max location problems.  Math. Oper. Res., 35(1):79–101, 2010.
  * [5] Daniel Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu.  Coresets for clustering in graphs of bounded treewidth.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 569–579. PMLR, 13–18 Jul 2020\.
  * [6] Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann.  New approximability results for the robust k-median problem.  In Scandinavian Workshop on Algorithm Theory, pages 50–61. Springer, 2014.
  * [7] Vladimir Braverman, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu.  Coresets for ordered weighted clustering.  In International Conference on Machine Learning, pages 744–753. PMLR, 2019.
  * [8] T.W. Byrka, J.and Pensyl, B. Rybicki, A. Srinivasan, and K. Trinh.  An improved approximation algorithm for k-median and positive correlation in budgeted optimization.  ACM Trans. Algorithms, 13(2)(23):1–31, 2013.
  * [9] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li.  Tight FPT Approximations for k-Median and k-Means.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1–42:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [10] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [11] Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala.  Socially fair k-means clustering.  In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 438–448, 2021.
  * [12] Mehrdad Ghadiri, Mohit Singh, and Santosh S Vempala.  Constant-factor approximation algorithms for socially fair $k$-clustering.  arXiv preprint arXiv:2206.11210, 2022.
  * [13] Dishant Goyal and Ragesh Jaiswal.  Tight fpt approximation for socially fair clustering.  Information Processing Letters, 182:106383, 2023.
  * [14] Sariel Har-Peled and Soham Mazumdar.  On coresets for k-means and k-median clustering.  In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, page 291–300, New York, NY, USA, 2004. Association for Computing Machinery.
  * [15] D.S. Hochbaum and D. Shmoys.  A best possible heuristic for the k-center problem.  Mathematics of Operation Research, 10(2):180–184, 1985.
  * [16] K. Jain and V. V. Vazirani.  Approximation algorithms for metric facility location and $k$-median problems using the primal-dual schema and Lagrangian relaxation.  J. ACM, 48(2):274–296, 2001.
  * [17] Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu.  A local search approximation algorithm for k-means clustering.  Computational Geometry, 28(2-3):89–112, 2004.
  * [18] Yury Makarychev and Ali Vakilian.  Approximation algorithms for socially fair clustering.  In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3246–3264. PMLR, 15–19 Aug 2021.
  * [19] Amnon Ta-Shma.  Explicit, almost optimal, $\epsilon$-balanced codes.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proc. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC’17), pages 238–251. ACM, 2017.

##  Appendix A Omitted Proof

######  Lemma A.1 (Ball decomposition lemma).

Consider a metric space $(X,\delta)$ with doubling dimension $d$. A subset
$A\subseteq X$ is $\epsilon$-dense in $X$, if $\forall x\in X$, $\exists y\in
A$ such that $\delta(x,y)\leq\epsilon$. $A$ is $\epsilon$-separated, if
$\forall x,y\in A$, $\delta(x,y)>\epsilon$ and $A$ is $\epsilon$-net of $X$ if
$A$ is $\epsilon$-separated as well as $\epsilon$-dense. Then we have the
following:

  1. 1.

There exists an $\epsilon$-dense set $A\subseteq{\sf ball}{(x,r)}$ of size
$(\frac{r}{\epsilon})^{O(d)}$ $\forall x\in X$, $r>0$, $\epsilon\leq r/2$.

  2. 2.

For all $\epsilon$-separated set $A\subseteq{\sf ball}{(x,r)}$, $r>0$,
$\epsilon\leq r/2$ it holds that $|A|\leq(\frac{r}{\epsilon})^{O(d)}$.

###### Proof.

  1. 1.

Let us denote $k$ as the doubling constant of the considered metric space
$(X,\delta)$ and $m=\lceil\log(r/\epsilon)\rceil$. Then by the definition, we
have $k=2^{O(d)}$. Note ball(x,r) can be covered with $k$ balls of radius
$r/2$. Further each of these balls of radius $r/2$ can be covered with $k$
balls of radius $r/4$ resulting the original ball ball(x,r) can be covered
with $k^{m}$ balls of radius $\frac{r}{2^{m}}$ (note
$\frac{r}{2^{m}}\leq\epsilon$). Again since $k=2^{O(d)}$, a simple calculation
shows that $k^{m}=(\frac{r}{\epsilon})^{O(d)}$. Let $A$ be the centers of
these balls then clearly $A$ is $\epsilon$-dense as required.

  2. 2.

Note that the balls of radius $(\frac{\epsilon}{2})$ around the points of $A$
are disjoint as the points in the set $A$ have pairwise distance strictly
greater than $\epsilon$ and further their union is included in the ${\sf
ball}{(x,r+\frac{\epsilon}{2})}$. Hence, $A$ is at most the size of any
$\epsilon/2$-dense set within the ${\sf ball}{(x,r+\frac{\epsilon}{2})}$. By
the previous claim, we finally prove that there exists an $\epsilon/2$-dense
set in ${\sf ball}{(x,r+\frac{\epsilon}{2})}$ of size
$(\frac{2r}{\epsilon})^{O(d)}$.
One can even construct the set $A$ greedily. Initially $A=\phi$. Next we
choose an arbitrary point in ball(x,r) and add it to $A$. Let $B$ denote the
union of the closed balls of radius $\epsilon$ around the points in $A$. As
long as we find a point $p\in{\sf ball}{(x,r)}\setminus B$, we add this
particular point to the set $A$. Note, when the algorithm stops the resulting
set $A$ becomes an $\epsilon$-net as both $\epsilon$-dense as well as
$\epsilon$-separated conditions are being satisfied.

∎