University of Bergen,
NorwayFedor.Fomin@uib.nohttps://orcid.org/0000-0003-1955-4612Supported by the
Research Council of Norway via the project BWCA (grant no. 314528). University
of Bergen,
NorwayPetr.Golovach@ii.uib.nohttps://orcid.org/0000-0002-2619-2990Supported by
the Research Council of Norway via the project BWCA (grant no. 314528). Indian
Institute of Technology Jodhpur, Jodhpur,
Indiataninamdar@gmail.comhttps://orcid.org/0000-0002-0184-5932 The Institute
of Mathematical Sciences, HBNI, Chennai, India and University of Bergen,
Norway saket@imsc.res.inhttps://orcid.org/0000-0001-7847-6402The author is
supported by the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (grant agreement No. 819416);
and he also acknowledges the support of Swarnajayanti Fellowship grant
DST/SJF/MSA-01/2017-18. Ben-Gurion University of the Negev, Beer-Sheva,
Israelmeiravze@bgu.ac.ilhttps://orcid.org/0000-0002-3636-5322The research was
supported by the European Research Council (ERC) grant no. 101039913
(PARAPATH). Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh,
Meirav Zehavi <ccs2012> <concept>
<concept_id>10003752.10003809.10003636.10003812</concept_id>
<concept_desc>Theory of computation Facility location and
clustering</concept_desc> <concept_significance>500</concept_significance>
</concept> <concept>
<concept_id>10003752.10003809.10010052.10010053</concept_id>
<concept_desc>Theory of computation Fixed parameter
tractability</concept_desc> <concept_significance>500</concept_significance>
</concept> </ccs2012> [500]Theory of computation Facility location and
clustering [500]Theory of computation Fixed parameter tractability Amit Kumar
and Noga Ron-Zewi 2 Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) APPROX/RANDOM
2024 APPROX/RANDOM 2024 August 28–30, 2024 London School of Economics, London,
UK 317 4

# Hybrid $k$-Clustering: Blending $k$-Median and $k$-Center

Fedor V. Fomin  Petr A. Golovach  Tanmay Inamdar  Saket Saurabh  Meirav Zehavi

###### Abstract

We propose a novel clustering model encompassing two well-known clustering
models: $k$-center clustering and $k$-median clustering. In the Hybrid
$k$-Clustering problem, given a set $P$ of points in $\mathbb{R}^{d}$, an
integer $k$, and a non-negative real $r$, our objective is to position $k$
closed balls of radius $r$ to minimize the sum of distances from points not
covered by the balls to their closest balls. Equivalently, we seek an optimal
$L_{1}$-fitting of a union of $k$ balls of radius $r$ to a set of points in
the Euclidean space. When $r=0$, this corresponds to $k$-median; when the
minimum sum is zero, indicating complete coverage of all points, it is
$k$-center.

Our primary result is a bicriteria approximation algorithm that, for a given
$\varepsilon>0$, produces a hybrid $k$-clustering with balls of radius
$(1+\varepsilon)r$. This algorithm achieves a cost at most $1+\varepsilon$ of
the optimum, and it operates in time
$2^{(kd/\varepsilon)^{\mathcal{O}(1)}}\cdot n^{\mathcal{O}(1)}$. Notably,
considering the established lower bounds on $k$-center and $k$-median, our
bicriteria approximation stands as the best possible result for Hybrid
$k$-Clustering.

###### keywords:

clustering, $k$-center, $k$-median, Euclidean space, fpt approximation

##  1 Introduction

Suppose we want to install a set of $k$ access points (APs) at certain
locations to provide wireless internet (Wi-Fi) coverage to a group of people
belonging to a certain area. Each AP is capable of providing Wi-Fi within a
circular-shaped region (i.e., a _disk_) of fixed radius $r$, and it may not be
possible to cover the entire region with $k$ such disks. Thus, after placing
$k$ APs, some people may be _outliers_ , that lie outside any of the $k$ disks
and do not receive Wi-Fi coverage. We can model this scenario as the classical
$k$-Center with Outliers problem, which is a crude model since it only cares
about the _number_ of outliers. However, our scenario is more nuanced. All
people that lie within any of the $k$ disks of radius $r$ already receive Wi-
Fi, whereas a person lying outside all of the $k$ disks must travel to the
boundary of the nearest disk in order to receive coverage. Naturally, we would
like to minimize the total distance traveled by people. Motivated by this and
several other problems in computational geometry/clustering, we consider the
following clustering problem, which encompasses two fundamental variants of
clustering: $k$-Center and $k$-Median. Given a set $P$ of points in some
metric space and integer $k$ and real $r\geq 0$, our objective is to position
$k$ closed balls of radius $r$ in a way that minimizes the sum of distances
from points uncovered by the balls to their closest balls. In Figure 1, we
provide an example of such clustering with $k=2$ and $r=2$.

$x$$y$$1$$2$$3$$4$$5$$6$$7$$8$$9$$1$$2$$3$$4$$5$$6$$7$$8$$9$ Figure 1: Two
disks of radius $2$ cover all except four points that are colored red. The
total sum of distances from these points to the yellow disks is
$2(1+\sqrt{8}-2)$.

To define the new clustering formally, we need some definitions. We consider
Euclidean inputs, i.e., all points belong to d for some $d\geq 1$ and the
distance function $\mathsf{dist}(\cdot,\cdot)$ is given by the Euclidean
($\ell_{2}$) distance. For a point $p\in P$ and a finite set of points
$Q\subset^{d}$, we define $\mathsf{dist}(p,Q)\coloneqq\min_{q\in
Q}\mathsf{dist}(p,q)$. Further, for $x,y\in P$, and a real $r\geq 0$, we
define the shorthand
$\mathsf{dist}_{r}(x,y)\coloneqq\max\left\\{\mathsf{dist}(x,y)-r,0\right\\}$.

Hybrid $k$-Clustering Input. A set $P\subset\mathbb{R}^{d}$ of $n$ points, an
integer $k\geq 1$, and a real $r\geq 0$. Task. Find a set
$F\subset\mathbb{R}^{d}$ of size at most $k$, that minimizes:
$\mathsf{cost}_{r}(P,F)\coloneqq\sum_{p\in P}\mathsf{dist}_{r}(p,F)$ (1)

We denote an instance of Hybrid $k$-Clustering as $\mathcal{I}=(P,k,r,d)$,
where $d$ denotes the dimension. When $r=0$, the optimal cost of Hybrid
$k$-Clustering equals the optimal $k$-Median clustering cost of the instance.
Thus in this case, Hybrid $k$-Clustering reduces to $k$-Median. However, when
$r>0$, $\mathsf{dist}_{r}(\cdot,\cdot)$ does not form a metric, and hence we
cannot simply reduce the problem to $k$-Median. On the other hand, the minimum
value $r$ that guarantees the cost of Hybrid $k$-Clustering to be zero is
equal to the optimal $k$-Center value. In this sense, Hybrid $k$-Clustering
reduces to $k$-Center.

Figure 2: Left: $k$-Center clustering, a special case of Hybrid $k$-Clustering
with $r=r^{\star}$. All points are covered by $k$ balls of radius $r^{\star}$
and ${\sf OPT}_{r^{\star}}=0$. Right: $k$-Median clustering, a special case of
Hybrid $k$-Clustering with $r=0$, and every point contributes its distance to
the closest center (some are shown as brown arrows). Middle: A general
instance of Hybrid $k$-Clustering lies somewhere _in between_ the two cases,
where points outside radius-$r$ balls contribute the distance to the boundary
(shown in blue).

###  1.1 Our Result and Techniques

The main result of this paper is a bicriteria approximation algorithm for
Hybrid $k$-Clustering. An $\alpha$-approximation to an instance
$\mathcal{I}=(P,k,r,d)$ is a subset $F\subset^{d}$ of size $k$ with
$\mathsf{cost}_{r}(P,F)\leq\alpha\cdot{\sf OPT}_{r}$, where ${\sf
OPT}_{r}\coloneqq\mathsf{cost}_{r}(P,F^{*})$ denotes the cost of an optimal
solution $F^{*}\subset^{d}$ of size at most $k$. Furthermore, an
$(\alpha,\beta)$-bicriteria approximation is a solution $F\subset^{d}$ with
$\mathsf{cost}_{\beta r}(P,F)\leq\alpha\cdot{\sf OPT}_{r}$. Here,
$\mathsf{cost}_{\beta r}(P,F)=\sum_{p\in P}\mathsf{dist}_{\beta r}(P,F)$.

Consider the special case of $r=r^{*}$, where $r^{*}$ is the optimal radius
for $k$-Center. Then, ${\sf OPT}_{r^{*}}=0$. Therefore, a
$(\alpha,1)$-bicriteria approximation would return a solution of cost
$\alpha\cdot{\sf OPT}_{r^{*}}=0$ using radius $1\cdot r^{*}$, i.e., an optimal
solution for $k$-Center. On the other hand, a $(1,\beta)$-bicriteria
approximation, for the special case of $r=0$, would return an optimal-cost
solution using the radius of $\beta r=0$. That is, such an algorithm would
optimally solve $k$-Median. Combining these observations with the established
lower bounds from the literature for $k$-Median and $k$-Center in Euclidean
spaces, implies the following bounds for Hybrid $k$-Clustering.

######  Proposition 1.1.

The following holds for Hybrid $k$-Clustering even when the input is from 2.

  * •

For any $\alpha\geq 1$, there exists no $FPT$ in $k$ algorithm that returns an
$(\alpha,1)$-approximation, unless FPT $=\mathsf{W}[1]$ [26].

  * •

For any finite $\beta\geq 1$, there exists no polynomial-time algorithm that
returns a $(1,\beta)$-approximation unless $\mathsf{P=NP}$ [28].

Further, assuming the Exponential-Time Hypothesis (ETH), if the input is from
d with $d\geq 4$, then there exists no $n^{o(k)}$ time algorithm that returns
a $(1,\beta)$-approximation, for any finite $\beta\geq 1$ [10].

Given these results, a natural question arises: _Can we achieve a
$(1+\varepsilon,1+\varepsilon)$-approximation for Hybrid $k$-Clustering,
running in time $f(k,\varepsilon)\cdot n^{\mathcal{O}(1)}$, particularly in
low-dimensional Euclidean spaces?_ Our main theorem answers this question.

######  Theorem 1.2.

Let $0<\varepsilon<1$. There exists a randomized algorithm that, given an
instance of Hybrid $k$-Clustering in d, runs in time
$2^{\left(\frac{kd}{\varepsilon}\right)^{\mathcal{O}(1)}}\cdot
n^{\mathcal{O}(1)}$, and returns a
$(1+\varepsilon,1+\varepsilon)$-approximation with probability at least a
positive constant.

This randomized algorithm and the proof of correctness are described in
Section 2. Here we discuss some of the main ideas. Recall that our objective,
as the problem name suggests, is a “hybrid” of $k$-Center and $k$-Median. In
our preprocessing steps, we first handle the inputs that behave _almost like_
either of the two problems. Suppose we (approximately) know the optimal value
of Hybrid $k$-Clustering for the given set of points $P$, called ${\sf
OPT}_{r}$. First, in Lemma 2.1, if $r>{\sf OPT}_{r}$, then we show that an
approximate solution can be found using techniques used for approximating
$k$-Center. Specifically, for each of the $k$ centers in the optimal solution,
we find a “nearby” center within distance $\epsilon r$ via overlaying a fine
grid in the space. Thus, we can assume that $r\leq{\sf OPT}_{r}$. Next, we
consider the case when $r$ is _too small_ compared to ${\sf OPT}_{r}$, namely,
when $r<\frac{\varepsilon{\sf OPT}_{r}}{n}$, and show that in this case, the
input behaves like $k$-Median– an approximate $k$-Median solution is also an
approximation for Hybrid $k$-Clustering (Lemma 2.3). In this manner, we
preprocess to handle inputs that resemble $k$-Center and $k$-Median, we obtain
a relation between $r$ and ${\sf OPT}_{r}$, which can be used to discretize
the distances, which can be used to bound the aspect ratio (i.e., the ratio of
maximum to minimum positive distance) (Lemma 2.5).

After the preprocessing step, we obtain inputs that are not _immediately
reducible_ to $k$-Center/Median. To handle such inputs, we design an intricate
recursive algorithm that, at each step, tries to simultaneously handle parts
(i.e., clusters) of the input that can be handled by either of the two
techniques. This algorithm is inspired by the sampling approach of Kumar,
Sabharwal, and Sen [23, 24] (also Jaiswal, Kumar, and Sen [22]). In this
approach, one first takes a large enough sample that can be used to pin down
the location of the largest cluster center. Then, one removes enough points
from the vicinity of this center, so that the next largest cluster becomes
dominant, and hence a subsequent sample contains sufficiently many points from
the second cluster, and so on.

Figure 3: Example of two different types of clusters. In each figure, we show
the cluster center in  red, a ball of radius $r$ around the center in green,
and a larger ball of radius $\mathcal{O}(r/\epsilon)$ in cyan with a dashed
outline. Left: A _$1$ -center-like_ cluster. Note that a large chunk of points
lies within the radius $\mathcal{O}(r/\varepsilon)$ ball around the center.
Right: A _$1$ -median-like_ cluster. Note that most of the points lie outside
the $\mathcal{O}(r/\epsilon)$ radius ball around
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c}$, and
for any such point, e.g.,  $p$ that is outside the
$\mathcal{O}(r/\varepsilon)$ radius ball,
$\mathsf{dist}_{r}({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c})\approx\mathsf{dist}({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c})$.

However, our scenario is more intricate and challenging for several reasons
due to the peculiar nature of the objective. Nevertheless, in principle, one
can classify each cluster as either being more _$1$ -center-like_, or more
_$1$ -median like_ (see Figure 3 for an illustration). In a _$1$ -center-like_
cluster, a large fraction of points lie within a ball of radius
$\mathcal{O}(r/\varepsilon)$. On the other hand, in a _$1$ -median-like_
cluster, a vast majority of points lie outside the
$\mathcal{O}(r/\varepsilon)$-radius ball. Note that any such point loses very
little due to the “$-r$” term in the clustering cost, i.e., its
$\mathsf{dist}_{r}$ and $\mathsf{dist}$ values are approximately equal.
Hypothetically, if we knew the partition of the input points into $k$
clusters, then we could use this classification to handle each type of cluster
separately – an almost-optimal center of a _$1$ -center-like_ cluster can be
found using a grid, whereas one can use an approximation for $1$-median (as a
black box) to handle a _$1$ -median-like_ cluster. However, the actual
clusters are obviously unknown to the algorithm. Hence, the algorithm has to
carefully navigate between the two types of clusters based on the random
sample obtained, and must simultaneously handle both scenarios using branching
(i.e., recursion). The analysis of the algorithm is also much more involved
due to the various cases in which the distinction between two types of
clusters is murkier. Nevertheless, we are able to show that the algorithm
returns a $(1+\varepsilon,1+\varepsilon)$-approximation in time
$2^{(kd/\varepsilon)^{\mathcal{O}(1)}}\cdot n^{\mathcal{O}(1)}$ with good
probability. Note that we incur an exponential dependence on the dimension $d$
due to “grid-arguments” used to handle _$1$ -center-like_ clusters, unlike the
approach of [23]. However, such dependence seems unavoidable using our
approach.

###  1.2 Related Problems

##### Euclidean Clustering.

An extensive body of literature exists on approximation algorithms for
$k$-Center and $k$-Median in the Euclidean space. For $k$-Median in d,
Polynomial-Time Approximation Schemes (PTASes) with a running time of
$n^{f(\epsilon,d)}$ have been developed, leveraging local search techniques
[17, 12]. Additionally, various Fixed-Parameter Tractable Approximation
Schemes (FPT-AS) with a running time of $f(k,d,\epsilon)\cdot
n^{\mathcal{O}(1)}$ are known for this problem [11, 13, 24, 22]. The
dependence on dimension $d$ can be eliminated through dimensionality reduction
techniques [25, 9].

For $k$-Center, an FPT-AS was introduced by Agarwal and Procopiuc in [4], with
a runtime of $\mathcal{O}(n\log k)+(k/\varepsilon)^{\mathcal{O}(dk^{1-1/d})}$
in d. Subsequent work by Badoiu, Har-Peled, and Indyk [5] improved the running
time to $2^{\mathcal{O}(k\log k)/\epsilon^{2}}$.

In [29], Tamir introduces a common generalization of the two clustering
problems, namely, $\ell$-centrum. In this problem, one ignores $\ell$ closest
points from the cost. Notably, $k$-Median ignores $0$ points, and $k$-Center
ignores all but one point. While this problem is related to Hybrid
$k$-Clustering, their objectives differ. Ordered $k$-Median, a further
generalization of $\ell$-Centrum, also does not align with our objective.
Approximation algorithms for this problem and some variants were developed in
[2, 1, 6, 7].

#####  $k$-center clustering with outliers.

In $k$-Center clustering, we are given sets $P$ (clients) and $\mathbb{F}$
(facilities) of points. Given an integer $k$, the task is to identify $k$
centers $F\subseteq\mathbb{F}$ minimizing the maximum distance of any point in
$P$ from its closest center. A popular variant of $k$-center is a formulation
that considers outliers. For a selected parameter $x$, up to $x$ points are
allowed not to be allocated to any center. A plethora of approximation
algorithms for this problem, and the related problems of covering points by
disks and minimum enclosing balls with outliers, exist in the literature [5,
14, 8, 18, 15, 16, 20, 27]. Hybrid $k$-Clustering could be seen as a variant
of $k$-Center with outliers, where we focus on the sum of distances to
outliers rather than their numbers.

##### Shape fitting.

A natural problem arising in machine learning, statistics, data-mining, and
many other fields is to fit a shape $\gamma$ to a set of points $P$ in
$\mathbb{R}^{d}$. Har-Peled in [19] introduces the following formalization of
this problem. For a family of shapes $\mathcal{F}$ (points, lines,
hyperplanes, spheres, etc.) we seek for a shape $\gamma\in\mathcal{F}$ with
the best fit to $P$. The typical criteria for measuring how well a shape
$\gamma$ fits a set of points $P$ could be the maximum distance between a
point of $P$ and its nearest point on $\gamma$ ($L_{\infty}$-fitting), sum of
the distances from $P$ to $\gamma$ ($L_{1}$-fitting) or the sum of the squares
of the distances ($L_{2}$-fitting). In this setting, Hybrid $k$-Clustering is
the problem of $L_{1}$-fitting to a shape from $\mathcal{F}$, where
$\mathcal{F}$ is the family of shapes defined by unions (not necessarily
disjoint) of $k$ balls in $\mathbb{R}^{d}$. Some relevant work in this
direction includes [3, 19, 21, 30].

##  2 Bicriteria FPT Approximation Scheme in Euclidean Spaces

We first set up some notation and define an important subroutine. For
$Y\subset^{d}$, and $y\in Y$, let $\mathsf{cl}(y,Y)\subseteq P$ denote the
subset of points of $P$, whose closest point in $Y$ is $y$. Ties are broken
arbitrarily. Note that $\left\\{\mathsf{cl}(y,Y):y\in Y\right\\}$ forms a
partition of $P$.

Let $p\in^{d}$ be a point and $\lambda\geq 0$, let
$B(p,\lambda)=\left\\{q\in^{d}:d(p,q)\leq\lambda\right\\}$ denote the ball of
radius $\lambda$ centered at $p$. For $0\leq\tau\leq\lambda$, let ${\sf
Grid}(p,\lambda,\tau)$ be the outcome of the following procedure: we place a
grid of sidelength $\tau/\sqrt{d}$ (of arbitrary offset). From each grid cell
$L$ that (partially) intersects with $B(p,\lambda)$ (i.e., $L$ contains a
point $q$ with $d(p,q)\leq\lambda$), we pick an arbitrary point from $L$ and
add it to the set ${\sf Grid}(p,\lambda,\tau)$. Note that ${\sf
Grid}(p,\lambda,\tau)$ can be computed in time proportional to the size of the
output. We have the following observations that follow from simple geometric
arguments.

  1. 1.

$|{\sf Grid}(p,\lambda,\tau)|\leq\mathcal{O}((\sqrt{d}\lambda/\tau)^{d})$,
where $d$ is the dimension.

  2. 2.

For any $q\in B(p,\lambda)$, there exists some $q^{\prime}\in{\sf
Grid}(p,\lambda,\tau)$ such that $d(q,q^{\prime})\leq\tau$.

###  2.1 Preprocessing

Suppose we know an estimate of ${\sf OPT}_{r}$ up to a constant factor – this
can be done by an exponential search or by first finding a bicriteria
(constant) approximation. For simplicity of exposition, we assume that we know
${\sf OPT}_{r}$ exactly.

##### Step 1.

Obtaining ${\sf OPT}_{r}\geq r\geq\frac{\varepsilon{\sf OPT}_{r}}{2n}$.

First, in the following lemma, we handle _$k$ -center-like_ instances, which
we can handle using “grid arguments”. If this is not applicable, we obtain
that $r\leq{\sf OPT}_{r}$.

######  Lemma 2.1.

If $r>{\sf OPT}_{r}$, then in time
$\left(\frac{d}{\varepsilon}\right)^{\mathcal{O}(dk)}\cdot
n^{\mathcal{O}(1)}$one can find a set $F\subset^{d}$ of size $k$, such that,
$\mathsf{cost}_{(1+\varepsilon)r}(P,F)\leq(1+\varepsilon){\sf OPT}_{r}$.

######  Proof 2.2.

Consider an optimal solution $F^{\star}$ such that
$\mathsf{cost}_{r}(P,F^{\star})={\sf OPT}_{r}$. We assume that $F^{\star}$ is
_minimal_ , i.e., no strict subset of $F^{\star}$ also yields the optimal
cost. It follows that every point $p\in P$ is within a distance of at most
$2r$ from some $c\in F^{\star}$, and each $c\in F^{\star}$ has some $p\in P$
within distance $2r$. Thus, $P$ can be covered using at most $k$ balls of
radius $2r$. Using a $2$-approximation for $k$-Center, we find a set $F$ such
that $P\subseteq\bigcup_{c\in F}B(c,4r)$. This implies that
$F^{\star}\subseteq\bigcup_{c\in F}B(c,6r)$.

Let $R=\bigcup_{c\in F}{\sf Grid}(c,6r,\varepsilon r)$. By Section 2, $|R|\leq
k\left(\frac{\sqrt{d}}{\varepsilon}\right)^{\mathcal{O}(d)}$. Now, we iterate
over all subsets $F^{\prime}\subseteq R$ of size at most $k$, and look at the
subset $F^{\prime}$ minimizing $\mathsf{cost}_{r}(P,F^{\prime})$. The number
of such subsets is at most $k\binom{|R|}{k}\leq
k\left(\frac{e|R|}{k}\right)^{k}\leq\left(\frac{d}{\varepsilon}\right)^{\mathcal{O}(dk)}$.
Also, by Section 2, there exists a subset $F\subseteq R$ of size at most $k$,
such that for each $c^{\star}\in F^{\star}$, there exists some $c^{\prime}\in
F$ such that $\mathsf{dist}(c^{\star},c^{\prime})\leq\varepsilon r$. It is
easy to see that $F$ satisfies the claimed properties.

In the following lemma, we handle _$k$ -median-like_ instances, where $r$ is
very small compared ${\sf OPT}_{r}$. We directly reduce such instances to
$k$-Median (where $r=0$). If this is not applicable, then we obtain that $r$
is not “too small” compared to ${\sf OPT}_{r}$.

######  Lemma 2.3.

Let $0<\varepsilon<1$. Suppose for an instance $\mathcal{I}$, ${\sf
OPT}_{r}\geq\frac{2nr}{\varepsilon}$. Then, ${\sf
OPT}_{0}\leq(1+\varepsilon/2)\cdot{\sf OPT}_{r}\leq(1+\varepsilon/2)\cdot{\sf
OPT}_{0}$. Furthermore, if $F\subset^{d}$ satisfies that
$\mathsf{cost}_{0}(P,F)\leq(1+\varepsilon/3)\cdot{\sf OPT}_{0}$. Then,
$\mathsf{cost}_{r}(P,F)\leq(1+\varepsilon)\cdot{\sf OPT}_{r}$. Such a set $F$
can be found in time $2^{(k/\varepsilon)^{\mathcal{O}(1)}}\cdot nd$.

######  Proof 2.4.

For any $F^{\prime}\subset^{d}$, it holds that
$\mathsf{cost}_{0}(P,F)\leq\mathsf{cost}_{r}(P,F^{\prime})+nr$. In particular,
let $F^{*}\subset^{d}$ be an optimal solution of size $k$, i.e.,
$\mathsf{cost}_{r}(P,F^{*})={\sf OPT}_{r}$. Then, it holds that
$\mathsf{cost}_{0}(P,F^{*})\leq\mathsf{cost}_{r}(P,F^{*})+n\cdot\frac{\varepsilon{\sf
OPT}_{r}}{2n}=(1+\varepsilon/2)\cdot{\sf OPT}_{r}$. Since
$\mathsf{cost}_{0}(P,F^{*})\geq{\sf OPT}_{0}$, since $F^{*}$ is a feasible
solution of size $k$ for $r=0$. This shows the first inequality.

Now, let $F\subset^{d}$ be a $(1+\varepsilon/3)$-approximate solution of size
$k$ for $\mathsf{cost}_{0}$, as in the statement of the lemma, i.e.,
$\mathsf{cost}_{0}(P,F)\leq(1+\varepsilon/3)\cdot{\sf OPT}_{0}$. Then, the
first inequality implies that
$\mathsf{cost}_{0}(P,F)\leq(1+\varepsilon/3)\cdot(1+\varepsilon/2)\cdot{\sf
OPT}_{r}\leq(1+\varepsilon)\cdot{\sf OPT}_{r}$. We can use a
$(1+\varepsilon/3)$-approximation algorithm (e.g., [23, 24]) for $k$-Median to
find such a solution.

For a given input $P$, we try the procedures from Lemma 2.1 and 2.3 and keep
them as candidate solutions. However, if $P$ does not satisfy the conditions
required to apply these lemmas, then we must have that $\frac{\varepsilon{\sf
OPT}_{r}}{2n}\leq r\leq{\sf OPT}_{r}$. In this case, we use the next step
before proceeding to the main algorithm.

##### Step 2.

Bounding the aspect ratio.

In this step, we suitably discretize the distances in order to bound the
aspect ratio of the metric (i.e., the maximum ratio of inter-point distances)
by $\mathcal{O}(\frac{n^{2}}{\varepsilon})$. This procedure preserves the cost
of an optimal solution up to a factor of $1+\varepsilon$.

######  Lemma 2.5.

Let $P$ be a set of points satisfying $\frac{\varepsilon{\sf OPT}_{r}}{2n}\leq
r\leq{\sf OPT}_{r}$. Then, in polynomial time we can obtain another (multi)set
of points $P^{\prime}$ such that, for any solution $F\subset^{d}$,
$\mathsf{cost}_{r}(P^{\prime},F)\in(1\pm\varepsilon)\cdot\mathsf{cost}_{r}(P,F)$,
and $\displaystyle\frac{\max_{p,q\in
P^{\prime}}\mathsf{dist}(p,q)}{\min_{p,q\in P^{\prime}:\mathsf{dist}(p,q)\neq
0}\mathsf{dist}(p,q)}\leq\frac{4n^{2}}{\varepsilon}$.

######  Proof 2.6.

Imagine an auxiliary graph $G=(P,E)$, where $pq\in E$ iff
$\mathsf{dist}(p,q)\leq 2({\sf OPT}_{r}+r)\leq 4{\sf OPT}_{r}$. If $G$ has
more than one connected component, then, note that two points belonging to
different connected components cannot belong to the same optimal cluster.
Hence, we can solve the problem separately on the points belonging to
different connected components and combine the solutions by a simple dynamic
programming.

Thus, we can handle each connected component of $G$ separately. In any
connected component, the maximum distance between any two points is at most
$n\cdot 4{\sf OPT}_{r}$. Now, we place a grid of sidelength
$\frac{\varepsilon{\sf OPT}_{r}}{\sqrt{d}n}$ and move each point $p\in P$ to
the center of the grid. It can be easily shown that this process does not
change the cost of an optimal solution by more than a $(1+\varepsilon)$
factor. Thus, the smallest non-zero inter-point distance is now at least
$\frac{\varepsilon{\sf OPT}_{r}}{n}$. Thus, the aspect ratio of the instance
is bounded by $\frac{4n^{2}}{\varepsilon}$.

Bounding the aspect ratio by $\mathcal{O}(\frac{n^{2}}{\varepsilon})$ means
that an exponential search over distances has at most
$\log_{2}\left(\frac{n^{2}}{\varepsilon}\right)=\mathcal{O}\left(\frac{\log(n)}{\varepsilon}\right)$
levels, which will be useful in our main algorithm. By slightly abusing the
notation, we continue to use $P$ for referring to the discretized (multi)set
$P^{\prime}$ returned by Lemma 2.5. If there are any co-located points in $P$,
we will treat them as separate points, and hence use set terminology instead
of multiset terminology.

After the two preprocessing steps, we now proceed to the description of the
main algorithm.

###  2.2 Main Algorithm

Our goal is to prove Theorem 1.2, that is, to design a randomized bicriteria
FPT approximation for Hybrid $k$-Clustering. We define some parameters. Let
$\delta\coloneqq\tfrac{\varepsilon}{10k}<\tfrac{1}{2}$,
$\delta^{\prime}\coloneqq\tfrac{\delta}{3}$ and
$r^{\prime}\coloneqq(1+\delta^{\prime})r$.

Algorithm 1 HybridClustering$(F^{\prime},k,m)$

1:$F^{\prime}\subseteq^{d}$ is a subset of centers of size at most $k-m$ added
to the solution so far

2:$\beta=\frac{1}{\delta^{c^{\prime}}}$ as required in Proposition 2.12 and
$\beta^{\prime}\coloneqq\beta\cdot\frac{150k}{\delta^{3}}$.

3:if $m=0$ then

4: return $F^{\prime}$

5:end if

6:$R\leftarrow\bigcup_{c^{\prime}\in F^{\prime}}{\sf
Grid}(c^{\prime},16r,\delta r)$

7:for each $q$ of the form $2^{j}$ in the range $[8r,\mathsf{dist}_{\max}]$ do

8: $P_{q}\coloneqq P\setminus\left(\bigcup_{c^{\prime}\in
F^{\prime}}B(c^{\prime},q)\right)$

9: Let $S_{q}$ be a sample of size $\beta^{\prime}$ chosen uniformly at random
from $P_{q}$

10: $R\leftarrow R\cup\bigcup_{p\in S_{q}}{\sf
Grid}(p,\frac{8r}{\delta},\delta r)$

11: for each $S\subseteq S_{q}$ of size $\beta$ do

12: $c^{\prime}\leftarrow\texttt{ApproxSolutionOnSample}(S,\delta/8)$
$\triangleright$ Algorithm from Proposition 2.12

13: $R\leftarrow R\cup\left\\{c^{\prime}\right\\}$

14: end for

15:end for

16:for each $c\in R\setminus F^{\prime}$ do

17: Call HybridClustering$(F^{\prime}\cup\left\\{c\right\\},k,m-1)$

18:end for

19:Call HybridClustering$(F^{\prime},k,m-1)$

20:return solution $\tilde{F}$ minimizing
$\mathsf{cost}_{r^{\prime}}(P,\tilde{F})$ over recursive calls made in lines
17 and 19

Algorithm 1 is a recursive algorithm, and is called HybridClustering. It takes
three parameters $F^{\prime},k$, and $m$. $F^{\prime}\subset^{d}$ is a subset
of centers added to the solution so far and has size $k-m$. Further, $k$ is
the total size of the solution, and $m$ is an upper bound on the remaining
solution (since we have already added $k-m$ centers). At a high (and
imprecise) level, the goal of each recursive step is to find an _approximate
replacement_ for each center in an unknown optimal solution.

In line 4, we check whether $m=0$, i.e., whether we have used our budget of
$k$ centers, and if so, we return the same set $F^{\prime}$ of centers built
through the recursive process. Otherwise (line 6 onward), we assume that
$m>0$, i.e., we are yet to add a set of centers. Throughout this process (line
6 to 15, we will build a set $R$ consisting of candidate centers, at least one
of which will be an approximate replacement of an _unseen_ center (i.e., one
whose approximate replacement has not already been found) from an optimal
solution. Finally, in line 17, we will make a recursive call by adding each
candidate to the current solution $F^{\prime}$. Now we discuss how we build
the set $R$.

First, in line 6, for each center $c^{\prime}\in F^{\prime}$ added so far, we
add a set of “nearby” centers by placing a grid. This handles the case when an
unseen optimal center is close to one of the already chosen centers in
$F^{\prime}$. Next, in the outer for loop (line 7 to 15), we handle the case
when all new optimal centers are relatively far from the already chosen
centers. In this for loop, we iterate over a range of values for the parameter
$q$ via exponential search. Parameter $q$ tries to approximate half of the
minimum distance between the already chosen and new optimal centers. Thus, for
the “correct” value of $q$, the set of points $C_{q}$ lying “far” from the
centers of $F^{\prime}$ (line 8), leaves all of the $m$ unseen optimal
clusters untouched. At this point, we aim to use a sample of faraway size
(chosen in line 9), to find an approximate replacement for one of these $m$
unseen centers. We do this by using the sample in two different ways, to
handle two different situations. First, if our sample happens to contain a
point “nearby” an unseen center, say $c^{\star}$, then the points chosen from
the fine grid in line 10 will find such an approximate replacement for
$c^{\star}$. Otherwise, the idea is that, if we have removed a significant
fraction of points from the “seen” clusters in line 8, by virtue of being
close to $F^{\prime}$, then the sample contains sufficiently many (i.e., at
least $\beta$) points from the largest unseen cluster, say $C^{\star}$, with
reasonable probability, and these points can be used to find an approximate
replacement of the cluster center (using Proposition 2.12). However, _a
priori_ we do not know which subset of the sample comes from $C^{\star}$.
Therefore, we iterate over all subsets of size $\beta$ in the inner for loop
(lines 11 to 14) to find such a subset of size $\beta$ that comes entirely
from $C^{\star}$ and use a known subroutine, called ApproxSolutionOnSample, to
find an approximate replacement. Finally, in 17, we make a recursive call by
adding each center from $R\setminus F^{\prime}$, and in line 19, we make a
recursive call by not adding any new center (to handle a particular case). In
line 20, we return the minimum-cost solution found over all recursive calls.
This completes the description of the algorithm.

###  2.3 Analysis

The crux of the analysis is to establish that Algorithm 1 satisfies the
following invariant.

#### Invariant

Let $0\leq m\leq k$ and $0<\alpha<1$ be a constant. Suppose for the given
$F^{\prime}$ of size at most $k-m$, there exists some $F=F^{\prime}\uplus
F_{o}\subset^{d}$, such that

  1. 1.

$|F_{o}|\leq m$, and

  2. 2.

$\sum_{c\in
F^{\prime}}\mathsf{cost}_{r^{\prime}}(\mathsf{cl}(c,F),c)+\sum_{c\in
F_{o}}\mathsf{cost}_{r}(\mathsf{cl}(c,F),c)\leq(1+\delta)^{k-m}\cdot{\sf
OPT}_{r}$ (2)

Then, with probability at least $\alpha^{m}$, the algorithm returns a solution
$\tilde{F}\subset^{d}$, such that

  1. 1.

$|\tilde{F}|\leq k$,

  2. 2.

$F^{\prime}\subseteq\tilde{F}$, and

  3. 3.

$\sum_{c\in\tilde{F}}\mathsf{cost}_{r^{\prime}}(\mathsf{cl}(c,F),c)\leq(1+\delta)^{k}\cdot{\sf
OPT}_{r}.$ (3)

#### Proof of Correctness.

The proof is by induction on $m$. For the base case, consider $m=0$. In the
base case (4), we return the same $F^{\prime}=F$ with probability one. In this
case, the invariant tells us that
$\mathsf{cost}_{r^{\prime}}(P,F)\leq(1+\delta)^{k}\cdot{\sf OPT}_{r}$, which
is what we need to prove. Now we assume that the claim is true for some
$m-1\geq 0$ and we prove it for $m$ by considering different cases.

##### Easy case: $F=F^{\prime}$.

This is a much simpler case since we have already found the desired set. In
this case, any solution $\tilde{F}$ returned by a recursive call always
contains $F=F^{\prime}$ as a subset. Then, in this case, we have that:

$\displaystyle\mathsf{cost}_{r^{\prime}}(P,\tilde{F})\leq\mathsf{cost}_{r^{\prime}}(P,F)\leq(1+\delta)^{k-m}\cdot{\sf
OPT}_{r}\leq(1+\delta)^{k}\cdot{\sf OPT}_{r}$

Here, the first inequality follows from the assumption that
$\tilde{F}\supseteq F=F^{\prime}$, and the second inequality follows from (2)
of the invariant. Note that we do not need to rely on the induction here.

##### Main case: $F^{\prime}\subsetneq F$.

This is the case where we are yet to discover some subset (namely, $F\setminus
F^{\prime}$) of centers. We will analyze this case by considering different
scenarios based on the inter-center distances, as well as their relative
sizes.

First, since $F^{\prime}\subsetneq F$, there exists some $c\in F\setminus
F^{\prime}$. Now, let $c\in F\setminus F^{\prime}$ and $c^{\prime}\in
F^{\prime}$ be the pair of centers with the smallest distance, i.e.,
$(c,c^{\prime})$ is a pair realizing $\min_{c_{1}\in F\setminus
F^{\prime},c_{2}\in F^{\prime}}\mathsf{dist}(c_{1},c_{2})$. Now we consider
different cases depending on $\mathsf{dist}(c,c^{\prime})$, namely the closest
distance between an already chosen center $c^{\prime}\in F^{\prime}$, and an
“unseen center” $c\in F\setminus F^{\prime}$.

##### Case 1. Nearby center: $\bm{\mathsf{dist}(c,c^{\prime})\leq 16r$}.$

In this case, via Section 2, we conclude that there exists some
$\tilde{c}\in{\sf Grid}(c^{\prime},16r,\delta r)$ with
$\mathsf{dist}(\tilde{c},c)\leq\delta r$. Let
$\tilde{F}=F^{\prime}\cup\left\\{\tilde{c}\right\\}$. Then, the proof follows
from the following claim (see Figure 4).

Figure 4: Illustration for Case 1. Centers in $F^{\prime}$ are shown as red
squares and unseen centers of $F\setminus F^{\prime}$ are shown as purple
crosses. $c$ is the closest center to  $F^{\prime}$ and
$\mathsf{dist}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}c},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}c^{\prime}})\leq
16r$. Then, a nearby center $\tilde{c}^{\prime}$ can be found using a $\delta
r$ grid.

######  Claim 1.

Let $c_{1}\in F_{o}$ and let $\tilde{c_{1}}\in^{d}$ be such that
$\mathsf{dist}(c_{1},\tilde{c_{1}})\leq\delta^{\prime}r$. Then, with
probability at least $\alpha^{m-1}$,
HybridClustering$(F\cup\tilde{c_{1}},k,m-1)$ returns a solution $\tilde{F}$
that satisfies the required properties.

######  Proof 2.7.

Consider $c_{1},\tilde{c_{1}}$ as defined in the statement. Let
$A=\mathsf{cl}(c_{1},F)$. For any point $p\in A$,
$\mathsf{dist}(p,\tilde{c_{1}})\leq\mathsf{dist}(p,c_{1})+\mathsf{dist}(c_{1},\tilde{c_{1}})\leq\mathsf{dist}(p,c_{1})+\delta^{\prime}r$.
This implies that,
$\mathsf{dist}_{r^{\prime}}(p,\tilde{c_{1}})\leq\mathsf{dist}_{r^{\prime}}(p,c_{1})$.
Define $F_{\text{new}}\coloneqq F^{\prime}_{\text{new}}\uplus F^{\prime}_{o}$,
where $F^{\prime}_{\text{new}}\coloneqq
F^{\prime}\cup\left\\{\tilde{c_{1}}\right\\}$ and $F^{\prime}_{o}\coloneqq
F_{o}\setminus\left\\{c_{1}\right\\}$. First, we show the following
inequality.

$\displaystyle\sum_{c\in
F^{\prime}_{\text{new}}}\mathsf{cost}_{r^{\prime}}(\mathsf{cl}(c,F),c)+$
$\displaystyle\sum_{c\in
F^{\prime}_{o}}\mathsf{cost}_{r}(\mathsf{cl}(c,F_{\text{new}}),c)$
$\displaystyle\leq$ $\displaystyle\sum_{c\in
F^{\prime}}\mathsf{cost}_{r^{\prime}}(\mathsf{cl}(c,F),c)+\sum_{c\in
F_{o}}\mathsf{cost}_{r}(\mathsf{cl}(c,F),c)$ (4)

We construct an assignment of clients to the centers in $F_{\text{new}}$,
where we may not assign a client to its closest center. To construct this
assignment, we consider different cases. For $c\in F^{\prime}\cup
F_{o}\setminus\left\\{c_{1}\right\\}$, we assign all points
$p\in\mathsf{cl}(c,F)$ to $c$. The contribution of all such points is the same
as the right-hand side of (4). Finally, we assign all points in
$\mathsf{cl}(c_{1},F)$ to $\tilde{c_{1}}$. By the choice of $\tilde{c}_{1}$,
$\mathsf{cost}_{r^{\prime}}(\mathsf{cl}(c_{1},F),\tilde{c_{1}})\leq\mathsf{cost}_{r}(\mathsf{cl}(c_{1},F),c_{1})$,
which is the contribution of such points on the right-hand side. Since the
cost on the left-hand side is no larger than the cost of the assignment thus
constructed, it shows (4).

Note that the right-hand side of (4) is at most $(1+\delta)^{k-m}\cdot{\sf
OPT}_{r}$ due to the invariant, and hence $F_{\text{new}}$ satisfies the
properties required to apply the inductive hypothesis for $m-1$. This implies
that with probability at least $\alpha^{m-1}$ the recursive call
Recursive$(F^{\prime}\cup\left\\{\tilde{c_{1}}\right\\},k,m-1)$ returns a
solution $\tilde{F}$ satisfying
$\mathsf{cost}_{r^{\prime}}(P,\tilde{F})\leq(1+\delta)^{k}\cdot{\sf OPT}_{r}$.

##### Case 2. Faraway center:
$\bm{16r<\mathsf{dist}(c,c^{\prime})\leq\mathsf{dist}_{\max}}$

. Let $t=\mathsf{dist}(c,c^{\prime})$ and $q^{\star}$ be the largest power of
$2$ that is at most $t/2$. Consider
$P_{q^{\star}}=P\setminus\left(\bigcup_{c_{1}\in
F^{\prime}}B(c_{1},q^{\star})\right)$. Let $c^{\star}\in F\setminus
F^{\prime}$ denote the center of the maximum-size cluster, i.e.,
$c^{\star}=\arg\max_{c_{1}\in F\setminus F^{\prime}}|\mathsf{cl}(c_{1},F)|$,
and $L\coloneqq\mathsf{cl}(c^{\star},F)$ denote the largest cluster. Finally,
let $D\coloneqq\bigcup_{c_{\text{old}}\in
F^{\prime}}\mathsf{cl}(c_{\text{old}},F)\cap P_{q^{\star}}$ denote the set of
clients that are distant from the respective centers in $F^{\prime}$. Let us
summarize some consequences of these definitions in the following observation
(its proof is essentially discussed above). Also see Figure 5.

Figure 5: Illustration for Case 2. Centers of
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}F^{\prime}}$
are shown as red squares and unseen centers of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}F\setminus
F^{\prime}}$ are shown as purple crosses. Balls of radius $q^{\star}$ around
$F^{\prime}$ are shown in dashed orange. $P^{\prime}$ are the points lying
outside these balls. Among the points of $P^{\prime}$, $D$ is the set of
points belonging to clusters around $F^{\prime}$, and shown as green-orange
filled dots. Finally, the cluster around
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}c}$ is the
largest unseen cluster (marked in dashed blue shape), $L$. We analyze
different cases depending on the relative sizes of $L$ and $D$.

  1. 1.

$\displaystyle P_{q_{\star}}=D\uplus\biguplus_{c_{1}\in F\setminus
F^{\prime}}\mathsf{cl}(c_{1},F)\cap P_{q^{\star}}$.

  2. 2.

In particular, $\mathsf{cl}(c,F),\mathsf{cl}(c^{\star},F)\subseteq
P_{q^{\star}}$.

We consider different sub-cases based on the relative sizes of $L$ and $D$.

##### Case 2.1. New cluster is tiny: $\bm{|L|\leq\delta^{2}/4\cdot|D|}$.

Let $N\coloneqq\mathsf{cl}(c,F)$. Note that the definition of $c^{\star}$,
combined with the case assumption, implies that
$|N|\leq|L|\leq\frac{\delta^{2}}{4}\cdot|D|$. We summarize a few technical
consequences of these definitions in the following claim.

######  Claim 2.

$\displaystyle\mathsf{cost}_{r}(N,c^{\prime})$
$\displaystyle\leq\delta\cdot\mathsf{cost}_{r}(D,F)+(1+\delta)\cdot\mathsf{cost}_{r}(N,c)$
(5)

######  Proof 2.8.

Note that for each $p\in D$, $\mathsf{dist}(p,F)\geq\frac{t}{4}$. Thus,
$\mathsf{dist}_{r}(p,c^{\prime})\geq\frac{t}{4}-r\geq\frac{3t}{16}$, where the
last inequality follows from the case assumption, namely $t>16r$. Thus, each
point $p\in D$ contributes at least $\frac{3t}{16}$ to
$\mathsf{cost}_{r^{\prime}}(P,F)$, and their total contribution to
$\mathsf{cost}_{r}(P,F)$ is

$\mathsf{cost}_{r}(D,F)\coloneqq\sum_{p\in
D}\mathsf{dist}_{r}(p,c^{\prime})\geq|D|\cdot\frac{3t}{16}$ (6)

Now we upper bound the cost of assigning points of $N$ to $c^{\prime}$. To
this end, we partition $N=N_{\text{near}}\uplus N_{\text{far}}$, where
$N_{\text{near}}\coloneqq\left\\{p\in A:\mathsf{dist}(p,c)\leq
2r/\delta\right\\}$ and $N_{\text{far}}\coloneqq\left\\{p\in
A:\mathsf{dist}(p,c)>2r/\delta\right\\}$. Note that, for each $p\in
N_{\text{far}}$,
$\mathsf{dist}_{r}(p,c)=\mathsf{dist}(p,c)-r\geq\mathsf{dist}(p,c)-\tfrac{\delta}{2}\cdot\mathsf{dist}(p,c)$,
which implies that, for each $p\in N_{\text{far}}$,

$\mathsf{dist}(p,c)\leq\left(\frac{1}{1-\tfrac{\delta}{2}}\right)\cdot\mathsf{dist}_{r}(p,c)\leq(1+\delta)\cdot\mathsf{dist}_{r}(p,c)$
(7)

Now consider,

$\displaystyle\mathsf{cost}_{r}(N,c^{\prime})$ $\displaystyle\leq\sum_{p\in
N}\mathsf{dist}(p,c^{\prime})$ (Since
$\mathsf{dist}_{r}(\cdot,\cdot)\leq\mathsf{dist}(\cdot,\cdot)$)
$\displaystyle\leq\sum_{p\in N}\mathsf{dist}(p,c)+\mathsf{dist}(c,c^{\prime})$
(Triangle inequality)
$\displaystyle=|N|\cdot\mathsf{dist}(c,c^{\prime})+\sum_{p\in
N_{\text{near}}}\mathsf{dist}(p,c)+\sum_{p\in
N_{\text{far}}}\mathsf{dist}(p,c)$
$\displaystyle\leq\tfrac{\delta^{2}}{8}\cdot|D|\cdot t+\sum_{p\in
N_{\text{near}}}\tfrac{4r}{\delta}+\sum_{p\in
N_{\text{far}}}(1+\delta)\cdot\mathsf{dist}_{r}(p,c)$ (From case assumption
and (7)) $\displaystyle=\tfrac{\delta^{2}}{4}\cdot|D|\cdot
t+\tfrac{4r}{\delta}\cdot|N_{\text{near}}|+(1+\delta)\cdot\mathsf{cost}_{r}(N,c)$
$\displaystyle\leq\tfrac{\delta^{2}}{4}\cdot|D|\cdot
t+\delta\cdot|D|\cdot\tfrac{t}{16}+(1+\delta)\cdot\mathsf{cost}_{r}(N,c)$
($|N_{\text{near}}|\leq|N|\leq\tfrac{\delta^{2}}{4}$ and $t>16r$)
$\displaystyle\leq|D|\cdot\tfrac{3t}{16}\cdot\delta\cdot\left(\tfrac{4\delta}{3}+\tfrac{1}{3}\right)+(1+\delta)\cdot\mathsf{cost}_{r}(N,c)$
$\displaystyle\leq\delta\cdot\mathsf{cost}_{r}(D,F)+(1+\delta)\cdot\mathsf{cost}_{r}(N,c)$
(8)

Where the last inequality follows from (6) and $\delta<1/2$.

Thus, consider the solution $F\setminus\left\\{c\right\\}$. To upper bound
$\mathsf{cost}_{r}(P,F\setminus\left\\{c\right\\})$, we assign all points in
$N=\mathsf{cl}(c,F)$ to $c^{\prime}$. The cost of this solution can be upper
bounded as follows

$\displaystyle\mathsf{cost}_{r}(P,F\setminus\left\\{c\right\\})$
$\displaystyle\leq\mathsf{cost}_{r}(P,F)-\mathsf{cost}_{r}(N,c)+\mathsf{cost}_{r}(N,c^{\prime})$
$\displaystyle\leq\mathsf{cost}_{r}(P,F)+\delta\cdot\mathsf{cost}_{r}(D,F)+\delta\cdot\mathsf{cost}_{r}(N,c)$
(From (5))
$\displaystyle\leq\mathsf{cost}_{r}(P,F)+\delta\cdot\mathsf{cost}_{r}(P,F)$
(Since $D\uplus N\subseteq P$) $\displaystyle\leq(1+\delta)^{k-m+1}\cdot{\sf
OPT}_{r}$ (9)

Where the last inequality follows from the invariant. Further, observe that
$c\in F\setminus F^{\prime}$, which implies that
$|(F\setminus\left\\{c\right\\})\setminus F^{\prime}|\leq m-1$. This, combined
with (9), shows that the solution
$F\setminus\left\\{c\right\\}=F^{\prime}\uplus(F_{o}\setminus\left\\{c\right\\})$
satisfies the conditions of the invariant for $m-1$. Then, by using inductive
hypothesis, $\texttt{HybridClustering}(F,k,m-1)$, with probability at least
$\alpha^{m-1}\geq\alpha^{m}$, returns a solution $\tilde{F}$ such that (a)
$|\tilde{F}|\leq k$, (b) $F\subseteq\tilde{F}$, and (c)
$\mathsf{cost}_{(1+\delta)r^{\prime}}(F,\tilde{F})\leq(1+\delta)^{k}\cdot{\sf
OPT}_{r}$, completing the induction.

##### Case 2.2. New cluster is large enough: $\bm{|L|>\delta^{2}/4\cdot|D|}$.

That is, the largest “untouched” cluster is at least an $\delta$ fraction of
the remaining points. Since $L=\mathsf{cl}(c^{\star},F)$ is the largest
“untouched” cluster, $|L|\geq|\mathsf{cl}(c_{1},F)|$ for all $c_{1}\in
F\setminus F^{\prime}$. Then, by Section 2.3, we have that,

$\displaystyle|P_{q^{\star}}|=|D|+\sum_{c_{1}\in F\setminus
F^{\prime}}|\mathsf{cl}(c_{1},F)|\leq|D|+|F\setminus F^{\prime}|\cdot|L|$
$\displaystyle\leq\tfrac{4}{\delta^{2}}\cdot|L|+k\cdot|L|\leq\tfrac{5k}{\delta^{2}}\cdot|L|$

In other words, $|L|\geq\frac{\delta^{2}}{5k}\cdot|P_{q^{\star}}|$.

In the next claim, we summarize some properties of the sample $S$ chosen in
line 7 of the algorithm, in the current case, i.e., when
$|L|\geq\frac{\delta^{2}}{5k}|C_{q^{\star}}|$.

######  Claim 3.

Consider the iteration of the for loop of 7, when $q=q^{\star}$, and the
corresponding sample $S_{q}$ obtained in 9. The following statements hold.

  1. 1.

With probability at least $1/2$, $S_{q}$ contains at least $\beta$ points of
$L$.

  2. 2.

$S_{q}\cap L$ has the same distribution as selecting $|S_{q}\cap L|$ points
uniformly at random from $L$.

  3. 3.

Let $L^{\prime}\subseteq L$ be an arbitrary subset of size at least
$\frac{\delta}{10}|L|$. Then, with probability at least $1/2$, $S_{q}$
contains at least $1$ point from $L$, i.e., $S_{q}\cap
L^{\prime}\neq\emptyset$.

######  Proof 2.9.

Recall that $\beta^{\prime}=\beta\cdot\tfrac{150k}{\delta^{3}}$ and
$|L|\geq\tfrac{\delta^{2}}{5k}|C_{q^{\star}}|$. So, the first item follows,
say, via Markov’s inequality 111In fact, a closer inspection reveals that the
probability is much closer to $1$, but “at least $1/2$” suffices for our
purpose.. The second item is an easy consequence of conditional distributions.
The proof of the third item is analogous to the first item, combined with the
bound on $|L^{\prime}|$.

Now we condition on the event that $|S_{q^{\star}}\cap L|\geq\beta$, which, by
3 happens with probability at least $\frac{1}{2}$. Then, let
$S^{\prime}\subseteq S\cap L$ be such a subset of size $\beta$. Let
$L=L_{\text{near}}\uplus L_{\text{far}}$, where $L_{\text{near}}=\left\\{p\in
L:\mathsf{dist}(p,c^{\star})\leq\tfrac{8r}{\delta}\right\\}$ and
$L_{\text{far}}=\left\\{p\in
L:\mathsf{dist}(p,c^{\star})>\tfrac{8r}{\delta}\right\\}$. We consider
different cases depending on the relative sizes of $L_{\text{near}}$ and
$L_{\text{far}}$. In the first case below (2.2.1), when $|L_{\text{near}}|$ is
not very tiny compared to $|L_{\text{far}}|$, we show that our sample contains
at least one point from $L_{\text{near}}$ with good probability, and hence an
$\varepsilon r$ grid around that point will contain an approximate center. In
the complementary case (2.2.2), $|L_{\text{near}}|$ is very tiny compared to
$|L_{\text{far}}|$, and in this case, we argue that, instead of finding an
approximate Hybrid $1$-Median, we can focus on finding an approximate
$1$-Median, which can be found using the sample. Now we formally analyze each
of these cases.

##### Case 2.2.1.
$\bm{|L_{\text{near}}|>\frac{\delta}{8}\cdot|L_{\text{far}}|}$.

In this case, letting $L^{\prime}\leftarrow L_{\text{near}}$ in 3, we infer
that with at least probability $1/2$, $S^{\prime}\cap
L_{\text{near}}\neq\emptyset$. We condition on this event. Then, since
$\mathsf{dist}(p,c^{\star})\leq\frac{8r}{\delta}$, it follows that there
exists a $\tilde{c}^{\star}\in{\sf Grid}(p,\frac{8r}{\delta},\delta r)$, such
that $\mathsf{dist}(\tilde{c}^{\star},c^{\star})\leq\delta r$. Since we branch
on each point in $\bigcup_{p^{\prime}\in S}{\sf
Grid}(p,\frac{8r}{\delta},\delta r)$, we will branch on $\tilde{c}^{\star}$ in
particular. Then, by 1,
HybridClustering$(F^{\prime}\cup\left\\{\tilde{c}^{\star}\right\\},k,m-1)$
returns a solution $\tilde{F}$, with probability at least
$1/2\cdot\alpha^{m-1}\geq\alpha^{m}$.

##### Case 2.2.2.
$\bm{|L_{\text{near}}|\leq\frac{\delta}{8}\cdot|L_{\text{far}}|}$.

We prove two claims, namely 4, and 5. The latter essentially reduces the
problem to finding an approximate solution to $1$-median on $L$. Intuitively
speaking, this follows from the following two reasons: (1) As we show in (10),
a similar statement holds for the points in $L_{\text{far}}$. This essentially
follows from the fact that, since each point of $L_{\text{far}}$ has distance
at least $\frac{8r}{\delta}$ to $c$, the subtraction of $r$ from their
distances has little effect on the cost, and (2) Due to the case assumption,
the points of $L_{\text{far}}$ vastly outnumber the points of
$L_{\text{near}}$. Hence, the preceding claim also translates to the points of
$L=L_{\text{far}}\cup L_{\text{near}}$, at a further small approximation
error.

######  Claim 4.

$\displaystyle\sum_{p\in L}\mathsf{dist}_{r}(p,c^{\star})\leq\sum_{p\in
L}\mathsf{dist}(p,c^{\star})\leq(1+\tfrac{3\delta}{4})\cdot\sum_{p\in
L}\mathsf{dist}_{r}(p,c^{\star})$.

######  Proof 2.10.

First, consider,

$\displaystyle\sum_{p\in
L_{\text{far}}}\mathsf{dist}_{r}(p,c^{\star})=\sum_{p\in
L_{\text{far}}}\mathsf{dist}(p,c^{\star})-r$ $\displaystyle\geq\sum_{p\in
L_{\text{far}}}\mathsf{dist}(p,c^{\star})-\tfrac{\delta}{8}\cdot\mathsf{dist}(p,c^{\star})$
(Since $\mathsf{dist}(p,c^{\star})\geq\frac{8r}{\delta}>r$)

Then, the inequality between the first and the last term can be rewritten as,

$\sum_{p\in
L_{\text{far}}}\mathsf{dist}(p,c^{\star})\leq\frac{1}{1-\delta/8}\cdot\sum_{p\in
L_{\text{far}}}\mathsf{dist}_{r}(p,c^{\star})\leq(1+\tfrac{\delta}{4})\cdot\sum_{p\in
L_{\text{far}}}\mathsf{dist}_{r}(p,c^{\star})$ (10)

The following inequality will be used later to show that the contribution of
points of $L_{\text{near}}$ is negligible to the overall cost.

$\displaystyle\sum_{p\in
L_{\text{far}}}\mathsf{dist}(p,c^{\star})\geq\sum_{p\in
L_{\text{far}}}\mathsf{dist}_{r}(p,c^{\star})$ $\displaystyle\geq\sum_{p\in
L_{\text{far}}}(1-\tfrac{\delta}{8})\cdot\mathsf{dist}(p,c^{\star})$ (From
(10))
$\displaystyle\geq(1-\tfrac{\delta}{8})\cdot\tfrac{8r}{\delta}\cdot|L_{\text{far}}|$
(Definition of $L_{\text{far}}$)
$\displaystyle\geq\tfrac{1}{2}\cdot\tfrac{8r}{\delta}\cdot\tfrac{8}{\delta}\cdot|L_{\text{near}}|$
(Case assumption: $|L_{\text{far}}|\geq\frac{8}{\delta}\cdot|L_{\text{far}}|$)
$\displaystyle=\tfrac{4}{\delta}\cdot\tfrac{8r}{\delta}\cdot|L_{\text{near}}|$
$\displaystyle\geq\tfrac{4}{\delta}\cdot\sum_{p\in
L_{\text{near}}}\mathsf{dist}_{r}(p,c^{\star})$ (11)

Where the last inequality follows from the definition of $L_{\text{near}}$.

The next sequence of inequalities shows a bound similar to (10), but when the
sum is taken over all points of $L$ (instead of only the points of
$L_{\text{far}}$, as in Equation 10).

$\displaystyle\sum_{p\in L}\mathsf{dist}_{r}(p,c^{\star})\leq\sum_{p\in
L}\mathsf{dist}(p,c^{\star})$ $\displaystyle=\sum_{p\in
L_{\text{near}}}\mathsf{dist}_{r}(p,c^{\star})+\sum_{p\in
L_{\text{far}}}\mathsf{dist}_{r}(p,c^{\star})$
$\displaystyle=(1+\tfrac{\delta}{4})\cdot\sum_{p\in
L_{\text{far}}}\mathsf{dist}(p,c^{\star})$ (From (11))
$\displaystyle\leq(1+\tfrac{\delta}{4})\cdot(1+\tfrac{\delta}{4})\cdot\sum_{p\in
L_{\text{far}}}\mathsf{dist}_{r}(p,c^{\star})$ (From (10))
$\displaystyle\leq(1+\tfrac{3\delta}{4})\cdot\sum_{p\in
L}\mathsf{dist}_{r}(p,c^{\star})$ (12)

Where the last inequality follows from (i)
$(1+\tfrac{\delta}{4})\cdot(1+\tfrac{\delta}{4})\leq 1+\tfrac{3\delta}{4}$ and
(ii) $L_{\text{far}}\subseteq L$. This completes the proof of the claim.

Using this claim, we prove the following claim, which shows that it is
sufficient to find an approximate $1$-median solution for $L$, which will also
be a good approximation for Hybrid $1$-Median for $L$. To this end, let
$\tilde{c}^{\star}\in^{d}$ denote the optimal $1$-median for $L$.

######  Claim 5.

Let $c_{1}$ be an $(1+\tfrac{\delta}{8})$-approximation for $1$-Median for
$L$, i.e., $\sum_{p\in
L}\mathsf{dist}(p,c_{1})\leq(1+\tfrac{\delta}{8})\cdot\sum_{p\in
L}\mathsf{dist}(p,\tilde{c}^{\star})$. Then, it is also a
$(1+\delta)$-approximation for Hybrid $1$-Median for $L$, i.e.,

$\sum_{p\in L}\mathsf{dist}_{r}(p,c_{1})\leq(1+\delta)\cdot\sum_{p\in
L}\mathsf{dist}_{r}(p,c^{\star})$ (13)

######  Proof 2.11.

Let $c_{1},\tilde{c}^{\star}\in^{d}$ as defined above. Then,

$\displaystyle\sum_{p\in L}\mathsf{dist}_{r}(p,c_{1})\leq\sum_{p\in
L}\mathsf{dist}(p,c_{1})$
$\displaystyle\leq(1+\tfrac{\delta}{8})\cdot\sum_{p\in
L}\mathsf{dist}(p,\tilde{c}^{\star})$ (By definition of $c_{1}$)
$\displaystyle\leq(1+\tfrac{\delta}{8})\cdot\sum_{p\in
L}\mathsf{dist}(p,c^{\star})$ (Since $c_{1}\in^{d}$ is an optimal $1$-median
and $c^{\star}\in^{d}$ is a feasible median)
$\displaystyle\leq(1+\tfrac{\delta}{8})\cdot(1+\tfrac{3\delta}{4})\cdot\sum_{p\in
L}\mathsf{dist}_{r}(p,c^{\star})$ (From 4)
$\displaystyle\leq(1+\delta)\cdot\sum_{p\in L}\mathsf{dist}_{r}(p,c^{\star})$

Thus, now the task reduces to finding a $1+\tfrac{\delta}{8}$-approximate
$1$-Median solution for $L$. To this end, we have the following result from
[23, 24].

######  Proposition 2.12 ([23, 24]).

Let $X\subset^{d}$ be a set of $n$ points and $0<\delta<1$. Let $S\subseteq X$
be a uniform sample chosen from $X$ of size
$\beta=\left(\frac{1}{\delta}\right)^{c^{\prime}}$. Then, there exists an
algorithm that runs in time $2^{\mathcal{O}(1/\delta^{c})}d$, and with
probability at least $\alpha^{\prime}$, returns an $(1+\delta)$-approximate
$1$-median for $X$. Here, $c,c^{\prime}$ are absolute constants independent of
the dimension $d$.

We combine the properties of the sample $S_{q^{\star}}$ proved in 3 along with
the previous proposition, to complete the proof. To this end, note that the
first item of 3 implies that, with probability at least $1/2$, $S_{q^{\star}}$
contains at least $\beta=\frac{1}{\delta^{c}}$ points from $L$. Then, we use
the algorithm of Proposition 2.12, that returns with probability at least
$\alpha^{\prime}$, a $(1+\frac{\delta}{8})$-approximate $1$-median
$c_{1}\in^{d}$ for $L$. It follows that,

$\displaystyle\sum_{c\in
F^{\prime}\cup\left\\{c_{1}\right\\}}\mathsf{cost}_{r^{\prime}}(\mathsf{cl}(c,F),c)+\sum_{c\in
F_{o}\setminus\left\\{c^{\star}\right\\}}\mathsf{cost}_{r}(\mathsf{cl}(c,F),c)$
$\displaystyle\leq$ $\displaystyle\sum_{c\in
F^{\prime}}\mathsf{cost}_{r^{\prime}}(\mathsf{cl}(c,F),c)+\sum_{c\in
F_{o}}\mathsf{cost}_{r}(\mathsf{cl}(c,F),c)-\mathsf{cost}_{r}(\mathsf{cl}(c^{\star},F),c^{\star})+\sum_{p\in
L}\mathsf{dist}_{r}(p,c_{1})$ $\displaystyle\leq$ $\displaystyle\sum_{c\in
F^{\prime}}\mathsf{cost}_{r^{\prime}}(\mathsf{cl}(c,F),c)+\sum_{c\in
F_{o}}\mathsf{cost}_{r}(\mathsf{cl}(c,F),c)-\mathsf{cost}_{r}(\mathsf{cl}(c^{\star},F),c^{\star})$
$\displaystyle+\delta\cdot\sum_{c\in
F_{o}}\mathsf{cost}_{r}(\mathsf{cl}(c,F),c)$ (From 5) $\displaystyle\leq$
$\displaystyle(1+\delta)\cdot\left(\sum_{c\in
F^{\prime}}\mathsf{cost}_{r^{\prime}}(\mathsf{cl}(c,F),c)+\sum_{c\in
F_{o}}\mathsf{cost}_{r}(\mathsf{cl}(c,F),c)\right)$ $\displaystyle\leq$
$\displaystyle(1+\delta)^{k-m+1}\cdot{\sf OPT}_{r}$ (14)

Then, by induction hypothesis,
HybridClustering$(F^{\prime}\cup\left\\{c_{1}\right\\},k,m-1)$, with
probability at least $\alpha^{m-1}$, returns a solution $\tilde{F}$ such that
$\mathsf{cost}_{r^{\prime}}(P,\tilde{F})\leq(1+\delta)^{k}\cdot{\sf OPT}_{r}$.
The overall probability of this event is at least
$\frac{1}{2}\cdot\alpha^{\prime}\cdot\alpha^{m-1}=\alpha^{m}$, completing the
induction.

This finishes the case analysis, and thus we have established the invariant
using induction. Using the invariant, we can show the following key lemma.

######  Lemma 2.13.

HybridClustering$(\emptyset,k,k)$ returns a
$(1+\varepsilon,1+\varepsilon)$-bicriteria approximation solution to the given
instance of Hybrid $k$-Clustering with probability at least $\alpha^{k}$ for
some constant $0<\alpha<1$.

######  Proof 2.14.

We first show the following:

######  Claim 6.

$\displaystyle|R|\leq\left(\tfrac{k\sqrt{d}}{\delta}\right)^{\mathcal{O}(d)}+\frac{k\log
n}{\delta^{\mathcal{O}(1)}}\cdot\left(\left(\tfrac{\sqrt{d}}{\delta}\right)^{\mathcal{O}(d)}+\binom{\beta^{\prime}}{\beta}\right)\leq(\log
n)\cdot 2^{(kd/\delta)^{\mathcal{O}(1)}}.$

######  Proof 2.15.

First, in 6, we add the points returned by ${\sf Grid}(c^{\prime},16r,\delta
r)$ for each $c^{\prime}\in F^{\prime}$. The number of such points is
$\left(\frac{16r\sqrt{d}}{\delta
r}\right)^{d}=\left(\frac{\sqrt{d}}{\delta}\right)^{\mathcal{O}(d)}$. Next,
there are at most $\frac{\log n}{\delta^{\mathcal{O}(1)}}$ values for $q$
(this follows from the second preprocessing step, cf. Lemma 2.5),
corresponding to each iteration of the for loop. In each iteration, we take a
sample $S$ of size
$\beta^{\prime}=\mathcal{O}{\left(\frac{150k\beta}{\delta^{3}}\right)}$. Then,
for each $p\in S$, we add to $R$ the points of ${\sf Grid}(p,8r/\delta,\delta
r)$, and the number of such points is at most
$\left(\frac{8\sqrt{d}}{\delta^{2}}\right)^{d}=\left(\frac{\sqrt{d}}{\delta^{2}}\right)^{\mathcal{O}(d)}$.
In addition, we iterate over each subset $S^{\prime}\subseteq S$ of size
$\beta$, and the number of such subsets is
$\binom{\beta^{\prime}}{\beta}\leq\left(\frac{e\beta^{\prime}}{\beta}\right)^{\beta}=\left(\frac{k}{\delta^{3}\cdot\beta}\right)^{\beta}=\left(\frac{k}{\delta^{3}}\right)^{(1/\delta)^{\mathcal{O}(1)}}=k^{1/\delta^{\mathcal{O}(1)}}$.
Thus, overall, the size of $R$ is bounded by $(\log n)\cdot
2^{(kd/\delta)^{\mathcal{O}(1)}}$.

To bound the running time of the algorithm, let $T(m)$ denote an upper bound
on
HybridClustering$(F^{\prime},k,m)$ for any $F^{\prime}\subset^{d}$. Note that
we make a recursive call on each point in $R$. Further by Proposition 2.12,
the time taken to compute a center in 12 is at most
$2^{(1/\delta)^{\mathcal{O}(1)}}$; and this algorithm is used in each of the
at most $\frac{k\log
n}{(1/\delta)^{\mathcal{O}(1)}}\cdot\binom{\beta^{\prime}}{\beta}\leq(\log
n)\cdot k^{\left(1/\delta\right)^{\mathcal{O}(1)}}$. Thus, $T(m)$ can be
bounded by the following recurrence.

$\displaystyle T(m)$ $\displaystyle\leq|R|\cdot T(m-1)+(\log n)\cdot
k^{\left(1/\delta\right)^{\mathcal{O}(1)}}\cdot n^{\mathcal{O}(1)}$
$\displaystyle\leq(\log n)\cdot
2^{\left(\frac{kd}{\delta}\right)^{\mathcal{O}(1)}}\cdot
T(m-1)+k^{\left(1/\delta\right)^{\mathcal{O}(1)}}\cdot n^{\mathcal{O}(1)}$

It can be shown that this recurrence solves to $T(m)\leq
2^{\left(\frac{kd}{\delta}\right)^{\mathcal{O}(1)}}\cdot n^{\mathcal{O}(1)}$ –
here we use the standard argument that $(\log n)^{k}\leq
k^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$.

Finally, note that our first call to the recursive algorithm is
HybridClustering$(F^{\prime}=\emptyset,k,k)$. At this point, the precondition
of the invariant is satisfying setting $F_{o}\leftarrow F^{*}$, an optimal
solution satisfying $\mathsf{cost}_{r}(P,F^{*})={\sf OPT}_{r}$. Then, the
correctness of the invariant implies that, with probability at least
$\alpha^{k}$, the algorithm returns a solution $\tilde{F}$ of size at most
$k$, that is a $(1+\varepsilon,1+\varepsilon)$-bicriteria approximation – here
we use that $\delta=\frac{\varepsilon}{10k}$, which implies that
$(1+\delta)^{k}\leq(1+\varepsilon)$.

We now conclude with the following theorem, which is restated for convenience.
See 1.2

######  Proof 2.16.

From Lemma 2.13, the success probability of the algorithm is $\alpha^{k}$ for
some constant $\alpha>0$. Thus, we need to repeat the algorithm $\alpha^{-k}$
times to boost the probability to at least a positive constant, which gets
absorbed in the $2^{\left(\frac{kd}{\varepsilon}\right)^{\mathcal{O}(1)}}$
factor.

#### A Hybrid of $k$-Center and $k$-Means.

We note that an almost identical algorithm also implies a
$(1+\varepsilon,1+\varepsilon)$ bicriteria approximation for an analogous
generalization of $k$-Center and $k$-Means. In this problem, the objective of
(1) is replaced by the following: $\mathsf{cost}_{r}(C,F)\coloneqq\sum_{p\in
C}\mathsf{dist}_{r}(p,C)^{2}$. Let us refer to this problem as Hybrid
$(k,2)$-Clustering – the “$2$” in the name refers to the squares of the
distance-thresholds that feature in the objective. Most of the analysis can be
adapted to deal with the squares of the distances, by appropriately changing
the sizes and distance-thresholds. The only significant change is that instead
of Proposition 2.12, one needs to use an algorithm that computes an
approximate $1$-Means solution given a large enough uniform sample of the
cluster – such an algorithm can also be found in [24]. Then, one obtains the
following theorem.

######  Theorem 2.17.

Let $0<\varepsilon<1$. There exists a randomized algorithm that, given an
instance of Hybrid $(k,2)$-Clustering in d, runs in time
$2^{(\frac{kd}{\varepsilon})^{\mathcal{O}(1)}}\cdot n^{\mathcal{O}(1)}$ and
returns a $(1+\varepsilon,1+\varepsilon)$-approximation with probability at
least a positive constant.

More generally, one can also define Hybrid $(k,z)$-Clustering analogously,
where the threshold-distances feature the $z$-th power of distances. Again,
our approach easily extends to this problem, modulo a version of Proposition
2.12 for the vanilla $(k,z)$-Clustering in Euclidean spaces. To the best of
our knowledge, such an algorithm is not explicitly known in the literature;
however, it may be possible to obtain such an algorithm using the approach of
[22, 24].

##  3 Conclusion and Future Directions

In this paper, we proposed a novel clustering objective and defined a new
problem, called Hybrid $k$-Clustering, that generalizes both $k$-Median and
$k$-Center. For $d$-dimensional euclidean inputs, we designed a randomized
$(1+\varepsilon,1+\varepsilon)$-bicriteria approximation scheme for Hybrid
$k$-Clustering running in time $2^{(kd/\varepsilon)^{\mathcal{O}(1)}}$, for
any $\varepsilon>0$. Further, essentially the same algorithm also generalizes
for a hybrid objective of $k$-Center and $k$-Means. We remind that improving
either of the two $(1+\varepsilon)$ factors to $1$ would imply an exact FPT
algorithm for $k$-Center/Median(/Means) in Euclidean spaces, which is unlikely
to exist.

Our work opens up several interesting research directions. An immediate
question is whether improving or removing the FPT dependence on the dimension
$d$ is possible, similar to the approach in [24] for $k$-Median/Means. One
potential direction for achieving this could be the recent result that imports
the famous Johnson-Lindenstrauss dimension reduction technique to
$k$-clustering problems [25]. Another intriguing question is the design of
coresets for Hybrid $k$-Clustering, which could also have some implications
for the previous problem via the approach of [9]. However, at a high level,
designing coresets for Hybrid $k$-Clustering appears to be challenging, since
_a priori_ we do not know which points belong inside the radius-$r$ balls (and
thus contribute $0$ to the cost), and which ones lie outside, and hence their
cost needs to be approximately preserved.

Finally, considering Hybrid $k$-Clustering with inputs from arbitrary metric
spaces, a primal-dual algorithm from [7] can be adapted to obtain an
$(\alpha,\beta)$-bicriteria approximation in polynomial time, for some
constants $\alpha$ and $\beta$ 222A quick examination of the proof of [7]
suggests that $(18,6)$-bicrtieria approximation easily follows, with further
improvements possible with more careful analysis.. Exploring the best possible
constants in the bicriteria approximation would be an interesting avenue for
future research.

## References

  * [1] Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase.  Parameterized approximation for robust clustering in discrete geometric spaces.  CoRR, abs/2305.07316, 2023.  URL: https://doi.org/10.48550/arXiv.2305.07316, arXiv:2305.07316, doi:10.48550/ARXIV.2305.07316.
  * [2] 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.  In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1377–1399. IEEE, 2023.  doi:10.1109/FOCS57990.2023.00085.
  * [3] Pankaj K. Agarwal, Sariel Har-Peled, and Hai Yu.  Robust shape fitting via peeling and grating coresets.  Discret. Comput. Geom., 39(1-3):38–58, 2008.  URL: https://doi.org/10.1007/s00454-007-9013-2, doi:10.1007/S00454-007-9013-2.
  * [4] Pankaj K. Agarwal and Cecilia Magdalena Procopiuc.  Exact and approximation algorithms for clustering.  Algorithmica, 33(2):201–226, 2002.  URL: https://doi.org/10.1007/s00453-001-0110-y, doi:10.1007/S00453-001-0110-Y.
  * [5] Mihai Badoiu, Sariel Har-Peled, and Piotr Indyk.  Approximate clustering via core-sets.  In Proceedings on 34th Annual ACM Symposium on Theory of Computing, (STOC), pages 250–257. ACM, 2002.  doi:10.1145/509907.509947.
  * [6] Jaroslaw Byrka, Krzysztof Sornat, and Joachim Spoerhase.  Constant-factor approximation for ordered k-median.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 620–631. ACM, 2018.  doi:10.1145/3188745.3188930.
  * [7] Deeparnab Chakrabarty and Chaitanya Swamy.  Interpolating between $k$-median and $k$-center: Approximation algorithms for ordered $k$-median.  In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107 of LIPIcs, pages 29:1–29:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.29, doi:10.4230/LIPICS.ICALP.2018.29.
  * [8] Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan.  Algorithms for facility location problems with outliers.  In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms (SODA), pages 642–651. ACM/SIAM, 2001.  URL: http://dl.acm.org/citation.cfm?id=365411.365555.
  * [9] Moses Charikar and Erik Waingarten.  The johnson-lindenstrauss lemma for clustering and subspace approximation: From coresets to dimension reduction.  CoRR, abs/2205.00371, 2022.  URL: https://doi.org/10.48550/arXiv.2205.00371, arXiv:2205.00371, doi:10.48550/ARXIV.2205.00371.
  * [10] Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, and Alan Roytman.  The bane of low-dimensionality clustering.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 441–456. SIAM, 2018.  doi:10.1137/1.9781611975031.30.
  * [11] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li.  Tight FPT approximations for $k$-median and $k$-means.  In 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICALP.2019.42.
  * [12] Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu.  Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics.  SIAM J. Comput., 48(2):644–667, 2019.  doi:10.1137/17M112717X.
  * [13] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn.  Towards optimal lower bounds for $k$-median and $k$-means coresets.  In Proceddings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1038–1051. ACM, 2022.  doi:10.1145/3519935.3519946.
  * [14] Mark de Berg, Leyla Biabani, and Morteza Monemizadeh.  $k$-center clustering with outliers in the MPC and streaming model.  In IEEE International Parallel and Distributed Processing Symposium, (IPDPS), pages 853–863. IEEE, 2023.  doi:10.1109/IPDPS54959.2023.00090.
  * [15] Hu Ding, Haikuo Yu, and Zixiu Wang.  Greedy strategy works for k-center clustering with outliers and coreset construction.  In 27th Annual European Symposium on Algorithms (ESA), volume 144 of LIPIcs, pages 40:1–40:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  URL: https://doi.org/10.4230/LIPIcs.ESA.2019.40, doi:10.4230/LIPICS.ESA.2019.40.
  * [16] Alon Efrat, Micha Sharir, and Alon Ziv.  Computing the smallest k-enclosing circle and related problems.  Comput. Geom., 4:119–136, 1994.  doi:10.1016/0925-7721(94)90003-5.
  * [17] Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour.  Local search yields a PTAS for k-means in doubling metrics.  SIAM J. Comput., 48(2):452–480, 2019.  doi:10.1137/17M1127181.
  * [18] Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan.  Approximation algorithms for partial covering problems.  Journal of Algorithms, 53(1):55–84, 2004.
  * [19] Sariel Har-Peled.  How to get close to the median shape.  Comput. Geom., 36(1):39–51, 2007.  URL: https://doi.org/10.1016/j.comgeo.2006.02.003, doi:10.1016/J.COMGEO.2006.02.003.
  * [20] Sariel Har-Peled and Soham Mazumdar.  Fast algorithms for computing the smallest k-enclosing circle.  Algorithmica, 41(3):147–157, 2005.  URL: https://doi.org/10.1007/s00453-004-1123-0, doi:10.1007/S00453-004-1123-0.
  * [21] Sariel Har-Peled and Yusu Wang.  Shape fitting with outliers.  SIAM J. Comput., 33(2):269–285, 2004.  doi:10.1137/S0097539703427963.
  * [22] Ragesh Jaiswal, Amit Kumar, and Sandeep Sen.  A simple D 2-sampling based PTAS for k-means and other clustering problems.  Algorithmica, 70(1):22–46, 2014.  URL: https://doi.org/10.1007/s00453-013-9833-9, doi:10.1007/S00453-013-9833-9.
  * [23] Amit Kumar, Yogish Sabharwal, and Sandeep Sen.  Linear time algorithms for clustering problems in any dimensions.  In 32nd International Colloquium on Automata, Languages and Programming (ICALP), volume 3580 of Lecture Notes in Computer Science, pages 1374–1385. Springer, 2005.  doi:10.1007/11523468\\_111.
  * [24] Amit Kumar, Yogish Sabharwal, and Sandeep Sen.  Linear-time approximation schemes for clustering problems in any dimensions.  J. ACM, 57(2):5:1–5:32, 2010.
  * [25] 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), pages 1027–1038. ACM, 2019.  doi:10.1145/3313276.3316350.
  * [26] Dániel Marx.  Efficient approximation schemes for geometric problems?  In 13th Annual European Symposium on Algorithms (ESA), volume 3669 of Lecture Notes in Computer Science, pages 448–459. Springer, 2005\.  doi:10.1007/11561071\\_41.
  * [27] Jirí Matousek.  On enclosing k points by a circle.  Inf. Process. Lett., 53(4):217–221, 1995.  doi:10.1016/0020-0190(94)00190-A.
  * [28] Nimrod Megiddo and Kenneth J Supowit.  On the complexity of some common geometric location problems.  SIAM journal on computing, 13(1):182–196, 1984.
  * [29] Arie Tamir.  The k-centrum multi-facility location problem.  Discret. Appl. Math., 109(3):293–307, 2001.  doi:10.1016/S0166-218X(00)00253-5.
  * [30] Hai Yu, Pankaj K. Agarwal, Raghunath Poreddy, and Kasturi R. Varadarajan.  Practical methods for shape fitting and kinetic data structures using coresets.  Algorithmica, 52(3):378–402, 2008.  URL: https://doi.org/10.1007/s00453-007-9067-9, doi:10.1007/S00453-007-9067-9.