Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering

Gadekar, Ameet; Inamdar, Tanmay

doi:10.4230/LIPIcs.STACS.2025.35

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering

Ameet Gadekar

CISPA Helmholtz Center for Information Security, Saarbrücken, Germany Tanmay Inamdar

Indian Institute of Technology Jodhpur, India

Abstract

Hybrid $k$ -Clustering is a model of clustering that generalizes two of the most widely studied clustering objectives: $k$ -Center and $k$ -Median. In this model, given a set of $n$ points $P$ , the goal is to find $k$ centers such that the sum of the $r$ -distances of each point to its nearest center is minimized. The $r$ -distance between two points $p$ and $q$ is defined as $\max\left\{\mathsf{dist}(p,q)-r,0\right\}$ – this represents the distance of $p$ to the boundary of the $r$ -radius ball around $q$ if $p$ is outside the ball, and $0$ otherwise. This problem was recently introduced by Fomin et al. [APPROX 2024], who designed a $(1+\varepsilon,1+\varepsilon)$ -bicrtieria approximation that runs in time $2^{(kd/\varepsilon)^{O(1)}}\cdot n^{O(1)}$ for inputs in $\mathbb{R}^{d}$ ; such a bicriteria solution uses balls of radius $(1+\varepsilon)r$ instead of $r$ , and has a cost at most $1+\varepsilon$ times the cost of an optimal solution using balls of radius $r$ .

In this paper we significantly improve upon this result by designing an approximation algorithm with the same bicriteria guarantee, but with running time that is FPT only in $k$ and $\varepsilon$ – crucially, removing the exponential dependence on the dimension $d$ . This resolves an open question posed in their paper. Our results extend further in several directions. First, our approximation scheme works in a broader class of metric spaces, including doubling spaces, minor-free, and bounded treewidth metrics. Secondly, our techniques yield a similar bicriteria FPT-approximation schemes for other variants of Hybrid $k$ -Clustering, e.g., when the objective features the sum of $z$ -th power of the $r$ -distances. Finally, we also design a coreset for Hybrid $k$ -Clustering in doubling spaces, answering another open question from the work of Fomin et al.

Keywords and phrases:

Clustering, Parameterized algorithms, FPT approximation,

k

-Median,

k

-Center

Funding:

Ameet Gadekar: Partially supported by the Israel Science Foundation (grant No. 1042/22).

Tanmay Inamdar: Supported by IITJ Research Initiation Grant (grant number I/RIG/TNI/20240072).

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Facility location and clustering ; Theory of computation

\rightarrow

Fixed parameter tractability

Related Version:

Full Version: https://arxiv.org/abs/2501.03663

Acknowledgements:

Tanmay would like to thank his co-authors from [23] – specifically Fedor V. Fomin – for formulating Hybrid

k

-Clustering problem and introducing him to it. This work was partially carried out while Ameet was at Bar-Ilan University, Israel.

DOI:

10.4230/LIPIcs.STACS.2025.35

Event:

42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Editors:

Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

$k$ -Center, $k$ -Median, and $k$ -Means are among the most popular clustering problems both in theory and practice, with numerous applications in areas such as machine learning [36, 28, 6, 11, 4, 9, 38, 25], facility location problems [32, 41, 30, 29, 35, 16], and computational geometry [7, 34], among others.¹¹1These citations are supposed not to be comprehensive, but representative–an interested reader may use them as a starting point for the relevant literature. All of these problems have long been known to be $\operatorname{NP}$ -hard, even in the plane [22, 40, 37]. To cope with these intractability results, there has been several decades of research on designing approximation algorithms for these problems, that have lead to polynomial-time constant-factor approximation algorithms for all of them in general metric spaces [27, 20]. Moreover, for more “structured” inputs – such as when the points belong to Euclidean spaces, or planar graph metrics – one can find near-optimal solutions using approximation schemes [24, 17, 19, 5, 34, 7, 2].²²2This includes polynomial-time as well as FPT approximation schemes. Furthermore, given the simplicity and ubiquity of these vanilla clustering objectives, the techniques used for obtaining these results are subsequently used to find clustering with additional constraints, such as capacities [18], fairness [8], and outliers [31, 3]. ${}^{\ref{foot:extensivecite}}$ One recurring theme in the literature has been to define a unified clustering objective that also captures classical clustering problems like $k$ -Median, $k$ -Center as special cases [42, 12, 15].

Along this line of research, Fomin et al. [23] recently introduced Hybrid $k$ -Clustering. In this problem, we are given an instance $\mathcal{I}=(M=(P,\mathbb{F},\mathsf{dist}),k,r)$ , where $M=(P,\mathbb{F},\mathsf{dist})$ is a metric space³³3Fomin et al. [23] only considered the special case of Euclidean inputs, i.e., when $P\subset\mathbb{F}=\real^{d}$ ; however, the underlying problem can be defined for arbitrary metric spaces. on the set of clients $P$ and a set of facilities $\mathbb{F}$ with distance function $\mathsf{dist}$ . Here, $k$ is a positive integer denoting the number of clusters, and $r$ is a non-negative real denoting the radius. The goal is to find a set $X\subseteq\mathbb{F}$ of $k$ centers, such that, $\mathsf{cost}_{r}(P,X)\coloneqq\sum_{p\in P}\mathsf{dist}_{r}(p,X)$ is minimized – here, for any point $p$ , any set $Q\subseteq P\cup\mathbb{F}$ , and a real $\alpha$ , $\mathsf{dist}_{\alpha}(p,Q)$ is defined as $\mathsf{dist}_{\alpha}(p,Q)\coloneqq\max\left\{\mathsf{dist}(p,Q)-\alpha,0\right\}$ , and $\mathsf{dist}(p,Q)\coloneqq\min_{q\in Q}\mathsf{dist}(p,q)$ . Fomin et al. [23] proposed several motivations for studying this cost function. Indeed, Hybrid $k$ -Clustering can be seen as a shape fitting problem, where one wants to find the “best” set of $k$ balls of radius $r$ that fit the given set of points, where the quality of the solution is determined by the sum of distances of each point to the nearest point on the boundary of the ball – this is analogous to the classical regression, where one wants to find the “best” linear function fitting the given set of points. Projective Clustering is a well-studied generalization of linear regression, where the aim is to find $k$ affine spaces that minimizes the sum of distances from the points to these spaces (see e.g., [43]), which is also closely related to the model considered in Hybrid $k$ -Clustering. Furthermore, [23] gave another motivation for studying Hybrid $k$ -Clustering– namely, placing $k$ WiFi routers with identical circular coverage, where the clients that lie outside the coverage area need to travel to the boundary of the nearest ball in order to receive coverage. Finally, the name of the problem is motivated from the fact that the objective is a kind of “hybrid” between the $k$ -Center and $k$ -Median costs, and generalizes both of them. Indeed, as observed in [23], Hybrid $k$ -Clustering with $r=0$ is equivalent to $k$ -Median, while, when $r$ is set to be the optimal radius for $k$ -Center, Hybrid $k$ -Clustering reduces to $k$ -Center. These observations immediately rule out uni-criteria polynomial-time approximation schemes that violate only the cost, or only the radius by any arbitrary factor $\alpha>1$ (as formalized in Proposition 1 of [23]). Indeed, such approximation algorithms – even with running times FPT in $k$ – would imply exact FPT algorithms for $k$ -Center and $k$ -Median in low-dimensional continuous Euclidean spaces. To our knowledge, such an algorithm for $k$ -Median is not known (nor is admittedly a lower bound), whereas [39] shows W[1]-hardness of $k$ -Center even in $\mathbb{R}^{2}$ . Therefore, given the current state of the art, a bicriteria approximation scheme for Hybrid $k$ -Clustering is essentially the best outcome, even if one allows a running time that is FPT in $k$ .

For $\alpha,\beta\geq 1$ , an $(\alpha,\beta)$ -bicrteria approximation for Hybrid $k$ -Clustering is an algorithm that returns a solution $X\subseteq\mathbb{F}$ of size at most $k$ satisfying $\mathsf{cost}_{\beta r}(P,X)\leq\alpha\cdot{\sf OPT}_{r}$ . Note that the bicriteria solution $X$ is allowed to consider $\mathsf{dist}_{\beta r}(p,X)=\max\left\{\mathsf{dist}(p,X)-\beta r,0\right\}$ instead of $\mathsf{dist}_{r}(p,X)$ and is also allowed to find a solution of cost $\alpha{\sf OPT}_{r}$ , where ${\sf OPT}_{r}$ is the cost of an optimal solution w.r.t. radius $r$ , i.e., without any violation of the radius. The main result of Fomin et al. [23] was an $(1+\varepsilon,1+\varepsilon)$ -bicriteria approximation for inputs in ^d in time $2^{(kd/\varepsilon)^{O(1)}}\cdot n^{O(1)}$ , where $n=|P|$ . An exponential dependence on the dimension $d$ appears inevitable using their approach, although it was not clear whether such a dependence is required. Indeed, for Euclidean $k$ -Median and $k$ -Center, one can obtain dimension-free approximation schemes with FPT dependence only on $k$ and $\varepsilon$ [7, 33, 1]. This naturally motivates the following question, which was explicitly asked as an open question in [23].

Question 1. “An immediate question is whether improving or removing the FPT dependence on the dimension $d$ is possible[…]”

In this work, we answer this question in the affirmative by designing a (randomized) bicriteria FPT Approximation Scheme (FPT-AS) parameterized by $k$ and $\varepsilon$ ⁴⁴4Such algorithms run in time $f(k,\varepsilon)n^{O(1)}$ and output a $(1+\varepsilon,1+\varepsilon)$ -bicriteria solution. Another term for FPT-AS is EPAS, which stands for Efficient Parameterized Approximation Schemes. for the (continuous) Euclidean instances of Hybrid $k$ -Clustering, stated formally in the following theorem.

Theorem 1 (Bicriteria FPT-AS for Euclidean Spaces).

There exists a randomized algorithm, that, given an instance of Hybrid $k$ -Clustering in ^d for any dimension $d$ , runs in time $2^{O\left(k\log k\cdot(\nicefrac{{1}}{{\varepsilon^{5}}})\log^{2}(\nicefrac{{1% }}{{\varepsilon}})\right)}\cdot n^{\mathcal{O}(1)}$ , and returns a $(1+\varepsilon,1+\varepsilon)$ -bicrtieria approximation with high probability.

The algorithm of [23] involves a pre-processing step that separately handles “ $k$ -Median-like”, “ $k$ -Center-like” instances, using the techniques specific to these respective problems. Then, the main algorithm handles the remaining instances that cannot be directly reduced to the respective problems. This approach somewhat undermines the goal of defining a unified problem that captures both of these problems as special cases. In contrast, our algorithm adopts a uniform approach by exploiting the intrinsic structure of the hybrid problem, without the need to separately handle some instances. In fact, our algorithm works for a broader class of metric spaces, called metric spaces of bounded algorithmic scatter dimension – a notion recently introduced by Abbasi et al. [1], and further studied by Bourneuf and Pilipczuk [10]. These metric spaces capture several interesting and well-studied metric spaces, see below. We give a formal definition of the notion of algorithmic scatter dimension in Section 2; however, a good mental picture to keep is to think of them as essentially doubling spaces, i.e., metric spaces with good “packing-covering” properties.⁵⁵5Although this is a good mental picture, it is ultimately inaccurate since the class of metric spaces of bounded algorithmic scatter dimension is strictly larger than that of doubling spaces. Indeed, continuous Euclidean space of high ( $\omega(\log n)$ ) dimension does not have bounded doubling dimension, yet it does have bounded algorithmic scatter dimension. Our general result is stated below.

Theorem 2 (Informal version of Theorem 9).

Hybrid $k$ -Clustering admits a randomized bicriteria FPT-AS in metrics of bounded algorithmic $\varepsilon$ -scatter dimension, parameterized by $k$ and $\varepsilon$ . In particular, Hybrid $k$ -Clustering admits randomized bicriteria FPT-AS parameterized by $k$ and $\varepsilon$ , in continuous Euclidean spaces of any dimension, metrics of bounded doubling dimension, bounded treewidth metrics, and by graphs from any fixed proper minor-closed graph class.

We give a technical overview of this result in Section 1.1, and describe the approximation algorithm and its analysis in Section 3.

In their work, [23] also defined Hybrid $(k,z)$ -Clustering problem, which features the $z$ -th power of $r$ -distances, i.e., the objective is to minimize $\mathsf{cost}_{r}(P,X,z)\coloneqq\sum_{p\in P}(\mathsf{dist}_{r}(p,X))^{z}$ , where $z\geq 1$ . They designed a bicriteria FPT-AS with similar running time for Hybrid $(k,2)$ -Clustering, i.e., a hybrid of $k$ -Means and $k$ -Center; but left the possibility of obtaining a similar result for the general case of $z\geq 1$ conditional on the existence of a certain sampling-based approximation algorithm for the $(k,z)$ -clustering problem for Euclidean inputs. Using our approach, we can obtain a bicriteria FPT-AS for any fixed $z\geq 1$ in a unified way, whose running time is independent of the dimension $d$ . In fact, our approach works for a much more general problem of Hybrid Norm $k$ -Clustering. We discuss these extensions in Section 4.

Next, we turn to another open direction mentioned in the work of Fomin et al. [23].

Question 2. “Another intriguing question is the design of coresets for Hybrid $k$ -Clustering, which could also have some implications for [Question 1].”

In this paper, we also answer this question affirmatively by designing coresets for Hybrid $k$ -Clustering in metric spaces of bounded doubling dimension. Specifically, we prove the following result.

Theorem 3 (Coreset for Hybrid $k$ -Clustering).

There exists an algorithm that takes as input an instance $\mathcal{I}=((P,\mathbb{F},\mathsf{dist}),k,r)$ of Hybrid $k$ -Clustering in doubling metric of dimension $d$ and a parameter $\varepsilon\in(0,1)$ , and in time $2^{O(d\log(1/\varepsilon))}|\mathcal{I}|^{O(1)}$ returns a pair $(P^{\prime},w)$ , where $P^{\prime}\subseteq P$ has size $2^{O(d\log(1/\varepsilon)}k\log|P|$ , and $w:P^{\prime}\to\mathbb{N}$ , such that the following property is satisfied for any $X\subseteq\mathbb{F}$ of size at most $k$ :

\left|{\sf wcost}_{r}(P^{\prime},X)-\mathsf{cost}_{r}(P,X)\right|\leq% \varepsilon\mathsf{cost}_{r}(P,X)

Here, ${\sf wcost}_{r}(P,X)\coloneqq\sum_{p\in P^{\prime}}w(p)\cdot\mathsf{dist}_{r}(% p,X)$ .

1.1 Technical Overview

In this section, we highlight our technical and conceptual contributions of our main result (Theorem 2).

A natural direction to design dimension-free parameterized approximation algorithm for Hybrid $k$ -Clustering is to leverage insights from the framework of Abbasi et al. [1], who designed dimension-free parameterized approximations for wide range of clustering problems. However, in Hybrid $k$ -Clustering, the objective is a function of $r$ -distances, instead of true distances, as in [1]. This introduces several technical challenges. For instance, a most obvious roadblock is that the $r$ -distances do not satisfy triangle inequality. Moreover, many of the “nice” properties that are enjoyed by the true distances in “structured” metric spaces (e.g., covering-packing property in doubling spaces, or properties of shortest paths in sparse graphs) do not extend readily to the $r$ -distances. Therefore, we have to overcome several technical and conceptual challenges in order to leverage the ideas presented in the framework of [1]. Let us first recall the key notion from this paper that is crucially used in this framework.⁶⁶6In fact, the algorithm of our paper and [1] works for a weaker notion called algorithmic scatter dimension. But, for ease of exposition, we work with scatter dimension in this section.

Scatter Dimension.

Informally, an $\varepsilon$ -scattering sequence in a metric space $M=(P,\mathbb{F},\mathsf{dist})$ is a sequence of center-point pairs $(x_{1},p_{1}),\dots,(x_{\ell},p_{\ell})$ , where $\ell$ is some positive integer and for $j\in[\ell],x_{j}\in\mathbb{F}$ , $p_{j}\in P$ such that $\mathsf{dist}(p_{j},x_{i})\leq 1$ , for all $1\leq j<i\leq[\ell]$ and $\mathsf{dist}(p_{i},x_{i})>(1+\varepsilon)$ , for all $i\in[\ell]$ . The $\varepsilon$ -scatter dimension of $M$ is the maximum length of $\varepsilon$ -scattering sequence contained in $M$ .

Now, consider a natural extension of the framework [1] for Hybrid $k$ -Clustering in a metric space $M$ as follows. Let ${\sf OPT}_{r}$ be the optimal cost of the Hybrid $k$ -Clustering instance corresponding to an optimal solution $O$ . The algorithm maintains cluster constraint $Q_{i}$ for each cluster $i\in[k]$ . Each $Q_{i}$ consists of a collection of requests of the form $(p,\delta)$ , where $p$ is a point and $\delta$ is a distance, representing the demand that $p$ requires a center within distance $\delta$ . The algorithm always maintains a solution $X$ such that $x_{i}\in X$ satisfy $Q_{i}$ cluster constraint, for all $i\in[k]$ . Now consider the sequence of triples $S_{i}=(x^{(1)}_{i},p_{i}^{(1)},\delta_{i}^{(1)}),\dots,(x^{(\ell)}_{i},p_{i}^{% (\ell)},\delta_{i}^{(\ell)})$ corresponding to requests in $Q_{i}$ , where $x^{(j)}_{i}$ is the $i^{\text{th}}$ center maintained by the algorithm just before adding request $(p_{i}^{(j)},\delta_{i}^{(j)})$ to $Q_{i}$ . If $X$ is a near-optimal solution, then the algorithm terminates successfully and returns $X$ . Otherwise, it identifies a point $p\in P$ whose $r$ -distance to $X$ is much larger than its $r$ -distance to $O$ . Such a point is called a witness to $X$ . A simple averaging argument shows that such a witness can be sampled with high probability. The algorithm then guesses the optimal cluster $i\in[k]$ of $p$ and add a new request $(p,\delta_{p}=\mathsf{dist}(p,X)/(1+\varepsilon^{\prime}))$ to $Q_{i}$ , for some suitable but fixed $\varepsilon^{\prime}$ depending on $\varepsilon$ . The center $x_{i}$ is recomputed to satisfy the updated cluster constraint $Q_{i}$ , if possible. Otherwise the algorithm reports failure.⁷⁷7E.g., if the algorithm failed to sample a witness. The key observation is that the sequence of pairs $(x^{(j_{1})}_{i},p_{i}^{(j_{1})}),\dots,(x^{(j_{\ell})}_{i},p_{i}^{(j_{\ell})})$ for a fixed radius $\delta_{i}^{(j)}$ forms an $\varepsilon$ -scattering sequence in $M$ . Thus, if the $\varepsilon$ -scatter dimension of $M$ is bounded then the length of these sequences are also bounded. Furthermore, it can be shown that if the aspect ratio of the radii of requests in $Q_{i}$ for all $i\in[k]$ is bounded, then the number of iterations of the algorithm can be bounded, yielding an FPT-AS.

Working with the inflated radius.

A major challenge that arises when the witness is defined in terms of $r$ -distances, but the requests added to the cluster constraints are based on the true distances. Specifically, we need to ensure that a witness whose $r$ -distance to $X$ is significantly larger than its $r$ -distance to $O$ also has a larger true distance to $X$ than to $O$ . This ensures that the request $(p,\mathsf{dist}(p,X)/(1+\varepsilon^{\prime}))$ is feasible and the algorithm does not fail. However, this condition may not hold, especially when the true distances are close to $r$ . In fact, the issue is related to a fundamental barrier identified by [23], assuming standard conjectures.⁸⁸8Such a framework could potentially yield a near-optimal solution that does not violate the radius, contradicting Proposition 1 in [23]. To overcome this fundamental barrier and maintain a sufficient gap between the true distances, we consider the cost of $X$ with respect to $(1+\varepsilon)r$ radius. In other words, we look for a solution $X$ whose $(1+\varepsilon)r$ -cost is close to ${\sf OPT}_{r}$ . In this case, we redefine a witness as a point in $P$ whose $(1+\varepsilon)r$ -distance to $X$ is much larger than its $r$ -distance to $O$ . These insights allow us to establish a gap between the true distance of a witness to $X$ and its true distance to $O$ , thereby justifying the requests added by the algorithm.

Bounding the aspect ratio of the radii.

Abbasi et al. [1] bound the aspect ratio of the radii by $(i)$ initializing the solution using “good” upper bounds, and $(ii)$ sampling witness from the points that have comparable distance to $X$ with respect to the corresponding upper bounds. The first step guarantees that the solution $X$ maintained by the algorithm always satisfies the upper bounds within constant factor. This together with the second step allows one to bound the aspect ratio of radii in each $Q_{i}$ . They show that such witnesses have a good probability mass if the points are sampled proportional to their true distances, and hence the algorithm successfully finds a witness for $X$ with probability that is a function of $k$ and $\varepsilon$ . Although, devising feasible and “good” upper bounds for Hybrid $k$ -Clustering can be done with some efforts, the main challenge arises in the second step, which only guarantees to sample a point whose $(1+\varepsilon)r$ -distance to $X$ is comparable with its upper bound. As mentioned before, these $(1+\varepsilon)r$ -distances can be much smaller than the corresponding true distances, and hence there is no guarantee that true distance of a witness $p$ to current solution $X$ is comparable to its upper bound. Towards this, we introduce a novel idea of dividing witnesses into two sets – “nearby witness” set, i.e., the set of points within distance $O(r/\varepsilon)$ from $X$ , and “faraway witness” set, which are beyond this distance from $X$ . The observation is that, since the total probability mass on the witness set, now defined using $(1+\varepsilon)r$ -distances, is still high, it must be that either the nearby or the faraway witnesses have sufficient probability mass. However, since we do not know which of the two sets has enough mass, we perform a randomized branching (i.e., make a guess) – which will be “correct” with probability $1/2$ . Then, when a point is sampled proportional to its $(1+\varepsilon)r$ -distance from either the “nearby” or “faraway” set, it will be a witness with good probability. Now consider each of two cases separately. Since for a nearby witness $p$ , its true distance to $X$ is at least $(1+\varepsilon)r$ and at most $O(r/\varepsilon)$ , the aspect ratio of the radii of requests corresponding to nearby witness set is bounded by $O(1/\varepsilon)$ . On the other hand, for requests corresponding to faraway witness set, we show that their radii lie in bounded interval, using ideas similar to [1]. Note that, these two arguments imply that the radii of the requests lie in two (possibly disjoint) intervals that themselves are bounded. However, it is not clear if the length of these requests is bounded, unlike [1], where the radii belonged to a single interval of bounded aspect ratio. Nevertheless, we observe that, using the techniques of [1], the length of requests can be bounded, even when the radii lie in constantly many (here, two) intervals, each with a bounded aspect ratio.

2 Background on Algorithmic Scatter Dimension

In this paper, we consider metric (clustering) space $M=(P,\mathbb{F},\mathsf{dist})$ , where $P$ is a finite set of $n$ points, $\mathbb{F}$ is a (possible infinite) set of potential cluster centers, and $\mathsf{dist}$ is a metric on $(P\cup\mathbb{F})$ . A class $\mathcal{M}$ of metric spaces is a (possibly infinite) set of metric spaces.

In this paper, we work with a notion that is weaker (and hence more general) than $\varepsilon$ -scatter dimension that was defined in the overview, called algorithmic $\varepsilon$ -scatter dimension, which we explain next. To this end, we first need the following search problem.

Definition 4 (Ball Intersection Problem).

Let $\mathcal{M}$ be a class of metric spaces with possibly infinite set of centers. Given $M=(P,\mathbb{F},\mathsf{dist})\in\mathcal{M}$ , a finite set $Q\subsetneq P\times\mathbb{R}_{+}$ of distance constraints, and an error parameter $\eta>0$ , the Ball Intersection problem asks to find a center $x\in F$ that satisfy all distance constraints within $\eta$ multiplicative error, i.e., $\mathsf{dist}(x,p)\leq(1+\eta)\delta$ , for every $(p,\delta)\in Q$ , if such a center exists, and report failure otherwise.

We say $\mathcal{M}$ admits a Ball Intersection algorithm if it correctly solves the ball intersection problem for every metric space in $M$ and runs in polynomial time in the size of $M$ and $1/\eta$ .

Now, we are ready to define algorithmic scatter dimension.

Definition 5 (Algorithmic $\varepsilon$ -Scatter Dimension).

Given a class $\mathcal{M}$ of metric spaces with Ball Intersection algorithm $\mathcal{C}_{\mathcal{M}}$ , a space $M\in\mathcal{M}$ , and $\varepsilon\in(0,1)$ , a $(\mathcal{C}_{\mathcal{M}},\varepsilon)$ -scattering sequence is a sequence $(x_{1},p_{1},\delta_{1}),\dots,(x_{\ell},p_{\ell},\delta_{\ell})$ , where $\ell$ is some positive integer, and for $i\in[\ell],x_{i}\in\mathbb{F}$ , $p_{i}\in P$ and $\delta_{i}\in\mathbb{R}_{+}$ such that

$\blacksquare$

(Covering by $\mathcal{C}_{\mathcal{M}}$ ) $x_{i}=\mathcal{C}_{\mathcal{M}}(M,\{(p_{1},\delta_{1}),\dots,(p_{i-1},\delta_{% i-1})\},\varepsilon/2)$ $\forall 2\leq i\leq\ell$
$\blacksquare$

( $\varepsilon$ -refutation) $\mathsf{dist}(x_{i},p_{i})>(1+\varepsilon)\delta_{i}$ $\forall i\in[\ell]$

The algorithmic $(\varepsilon,\mathcal{C}_{\mathcal{M}})$ -scatter dimension of $\mathcal{M}$ is $\lambda_{\mathcal{M}}(\varepsilon)$ if any $(\mathcal{C}_{\mathcal{M}},\varepsilon)$ -scattering sequence contains at most $\lambda_{\mathcal{M}}(\varepsilon)$ many triples per radius value. The algorithmic $\varepsilon$ -scatter dimension of $\mathcal{M}$ is the minimum algorithmic $(\varepsilon,\mathcal{C}_{\mathcal{M}})$ -scatter dimension over any Ball Intersection algorithm $\mathcal{C}_{\mathcal{M}}$ for $\mathcal{M}$ .

Although, algorithmic scatter dimension restricts the number of triples in the sequence with same radius value, we can use the proof technique from [1] to prove the following stronger guarantee. Results marked with $\spadesuit$ can be found in the full version of the paper.

Lemma 6 ( $\spadesuit$ ).

Let $\mathcal{M}$ be a class of metric spaces of algorithmic $\varepsilon$ -scatter dimension $\lambda(\varepsilon)$ . Then there exists a Ball Intersection algorithm $\mathcal{C}_{\mathcal{M}}$ with the following property. Given $\varepsilon\in(0,1)$ , a constant $t\geq 1$ , and $a_{i}>0,\tau_{i}\geq 2$ for $i\in[t]$ , any $(\mathcal{C}_{\mathcal{M}},\varepsilon)$ -scattering contains $O(\sum_{i\in[t]}\lambda(\nicefrac{{\varepsilon}}{{2}})(\log\tau_{i})/\varepsilon)$ many triples whose radii lie in the interval $\cup_{i\in[t]}[a_{i},\tau_{i}a_{i}]$ .

3 Bicriteria FPT Approximation Scheme

3.1 Algorithm

Algorithm 1 Approximation Scheme for Hybrid

k

-Clustering.

Our bicrteria FPT-AS for Hybrid $k$ -Clustering is formally stated in Algorithm 1. As an input, we are given an instance $\mathcal{I}=((P,\mathbb{F},\mathsf{dist}),k,r)$ of Hybrid $k$ -Clustering, an accuracy parameter $\varepsilon$ , access to an algorithm $\mathcal{C}$ for the so-called “Ball Intersection” problem (discussed later), and a guess $\mathcal{G}$ for the optimal cost ${\sf OPT}_{r}$ . By a standard exponential search, we will assume that ${\sf OPT}_{r}\leq\mathcal{G}\leq(1+\varepsilon/3)\cdot{\sf OPT}_{r}$ . At a high level, this algorithm can be divided into two steps: initialization phase and the iterative cost-improvement phase. The initialization phase spans from line 1 to 7.

At a high level, the goal of this phase to compute for each point $p\in P$ , an upper bound $u(p)$ , such that $p$ must have an optimal center within distance $u(p)$ . Once we find such upper bounds, we use a subset of them to initialize for each $i\in[k]$ , a set of requests $Q_{i}$ , where each request $(p,\delta_{p})$ demands that the $i$ th center in the solution must be within distance at most $\delta_{p}$ from $p$ in every subsequent solution found by the algorithm.

Now, the algorithm moves to the iterative cost-improvement phase in lines 8 to 20, consisting of a while loop that runs as long as the current solution has not become the bicriteria approximation that we are looking for. Thus, in each iteration of the while loop, we are given a solution $X$ that satisfies all the requests $Q_{i}$ , and yet satisfies $\mathsf{cost}_{r^{\prime}}(P,X)>(1+\varepsilon)\cdot\mathcal{G}$ . Then, our algorithm makes a random choice whether there is enough cost-contribution of nearby witnesses, or of faraway witnesses – here a witness is a point $p$ whose distance to $X$ is sufficiently larger than that in the (unknown) optimal solution $O$ . In each of the cases, we sample points from carefully defined sets (cf. $N$ in line 11 and $A$ in 14), proportional to their contribution to the cost to the respective sets (in the analysis, we will argue that with good probability, we will in fact sample witness points). Having sampled such a point $p$ , we guess the index $i$ of the optimal cluster of $p$ in line 17. Finally, assuming $p$ is indeed a witness, we add a request $(p,\frac{\mathsf{dist}(p,X)}{1+\varepsilon/12})$ to the $i$ th request set $Q_{i}$ , and in line 19 we recompute $x_{i}$ using $\mathcal{C}$ . This algorithm either returns a center $x_{i}\in\mathbb{F}$ that satisfies all the requests (with an error of up to a factor of $\varepsilon/40$ ), or correctly outputs that there is no point in $\mathbb{F}$ satisfying all the requests. Note that in discrete metric spaces, $\mathcal{C}$ can be simulated by simply scanning each $x\in\mathbb{F}$ and checking whether it satisfies all the requests in $Q_{i}$ . On the other hand, for continuous Euclidean spaces, such an algorithm was designed in [1]. If the algorithm does not fail at this step, then we update our set $X$ and continue to the next iteration. In the rest of the section, we will prove that the algorithm returns a $(1+\varepsilon,1+\varepsilon)$ -bicriteria approximation with good probability.

3.2 Analysis

Throughout the analysis, we assume that we are given a guess $\mathcal{G}$ , such that ${\sf OPT}_{r}\leq\mathcal{G}\leq(1+\varepsilon/3)\cdot{\sf OPT}_{r}$ . We divide the analysis in two parts. In the first part, we bound the running time of the algorithm using the following lemma. The proof of this lemma is present in Section 3.2.1.

Lemma 7.

Algorithm 1 terminates in $O(\frac{k}{\varepsilon}\log(\frac{k}{\varepsilon})\lambda(\frac{\varepsilon}{4% 0}))$ iterations – with or without failure.

In the second part, we show the following lemma, which says that the probability that the algorithm terminates without failure is high. The proof the lemma is present in Section 3.2.2.

Lemma 8.

With probability at least $\exp\left(-O\left(\frac{k}{\varepsilon}\log(\frac{k}{\varepsilon})\lambda(% \frac{\varepsilon}{40})\right)\right)$ , Algorithm 1 terminates without failure, i.e., returns a solution $X$ satisfying $\mathsf{cost}_{(1+\varepsilon/3)r}(P,X)\leq(1+\varepsilon){\sf OPT}_{r}$ .

Using these two lemmas and repeating the algorithm $\exp\left(O\left(\frac{k}{\varepsilon}\log(\frac{k}{\varepsilon})\lambda(\frac% {\varepsilon}{40})\right)\right)$ times, we have our main result.

Theorem 9 (Main Theorem).

Let $\mathcal{M}$ be a class of metric spaces closed under scaling distances by a positive constant. There is a randomized algorithm that takes as input an instance $\mathcal{I}=((P,\mathbb{F},\mathsf{dist}),k,r)$ of Hybrid $k$ -Clustering such that $(P,\mathbb{F},\mathsf{dist})\in\mathcal{M}$ and $\varepsilon\in(0,1)$ , and outputs a $(1+\varepsilon,1+\varepsilon)$ -bicriteria solution for $\mathcal{I}$ when, for all $\varepsilon^{\prime}>0$ , the algorithmic $\varepsilon^{\prime}$ -scatter dimension of $\mathcal{M}$ is bounded by $\lambda(\varepsilon^{\prime})$ , for some function $\lambda$ . The running time of the algorithm is $2^{O(\frac{k}{\varepsilon}\cdot\log(k/\varepsilon)\cdot\lambda(\varepsilon/40)% )}\cdot|{\mathcal{I}}|^{O(1)}$ .

3.2.1 Bounding runtime using Algorithmic Scatter Dimension

First, we show some properties of the initial upper bounds (line 4), that we need later in the proof of Lemma 7.

Lemma 10 (Feasible upper bounds).

Consider $Q_{i}=\{(p^{(i)},u(p^{(i)}))\}$ initialized in Line 4 of Algorithm 1. Then, $\mathsf{dist}(p^{(i)},O)\leq u(p^{(i)})$ .

Proof.

Suppose $\mathsf{dist}(p^{(i)},O)>u(p^{(i)})$ . Letting $\alpha=u(p^{(i)})/3$ , we have that $|{\sf ball}(p,\alpha)|\geq\mathcal{G}/\alpha$ . Since, $\mathsf{dist}(p^{(i)},O)>3\alpha$ , we have $\mathsf{dist}(p,O)>2\alpha$ for $p\in{\sf ball}(p^{(i)},\alpha)$ . Using $\alpha>r$ , this means $\mathsf{dist}_{r}(p,O)>\alpha$ for $p\in{\sf ball}(p,\alpha)$ . Therefore,

\mathsf{cost}_{r}(P,O)\geq\sum_{p\in{\sf ball}(p^{(i)},\alpha)}\mathsf{dist}_{% r}(p^{\prime},O)=\sum_{p\in{\sf ball}(p^{(i)},\alpha)}(\mathsf{dist}(p,O)-r)>% \frac{\mathcal{G}}{\alpha}\cdot\alpha=\mathcal{G},

contradicting the the cost of $O$ . $\hfill\blacktriangleleft$

Next, we have the following lemma, whose proof is identical to [1], that says that the initialization of $X$ at line 6 is successful and the solution maintained by the algorithm always satisfies the upper bounds within a factor of $3.1$ .

Lemma 11 (Lemma V.5 of [1]).

The number of marked points in line 3 is at most $k$ , i.e., $k^{\prime}\leq k$ . Hence, the initialization of $X$ at line 6 is successful. Furthermore, at any iteration, the solution $X$ maintained by the algorithm satisfies that $\mathsf{dist}(p,X)\leq 3.1u(p)$ , for every $p\in P$ .

Bounding aspect ratio of radii

Towards proving Lemma 7, we bound the aspect ratio of the radii in the requests.

Lemma 12.

Consider a request set $Q_{i}=\{(p^{(1)}_{i},\delta^{(1)}_{i}),\dots,(p^{(\ell)}_{i},\delta^{(\ell)}_{% i})\}$ , for $i\in[k]$ . Let $X^{(j)},j\in[\ell]$ , be the center maintained by the algorithm just before adding the request $(p^{(j)}_{i},\delta^{(j)}_{i})$ to $Q_{i}$ . Further, let $x^{(j)}_{i}\in X^{(j)}$ be the center corresponding to cluster $i\in[k]$ . Then, the sequence $S_{i}=(x^{(1)}_{i},p^{(1)}_{i},\delta^{(1)}_{i}),\dots,(x^{(\ell)}_{i},p^{(% \ell)}_{i},\delta^{(\ell)}_{i})$ is an algorithmic $(\mathcal{C},\nicefrac{{\varepsilon}}{{20}})$ -scattering. Furthermore, the radii of requests in $S_{i}$ lie in the interval $[r,8r/\varepsilon]\cup[r_{min},\frac{10^{5}k}{\varepsilon^{2}}r_{min}]$ , where $r_{min}$ is the smallest radii in $S_{i}$ that is larger than $8r/\varepsilon$ .

Proof.

The proof of the first part is similar to [1].

First note that $\delta^{(j)}_{i}=\frac{\mathsf{dist}(p^{(j)}_{i},X^{(j)})}{1+\nicefrac{{% \varepsilon}}{{12}}}\leq\frac{\mathsf{dist}(p^{(j)}_{i},x^{(j)}_{i})}{1+% \nicefrac{{\varepsilon}}{{12}}}$ . Finally, since $x^{(j)}_{i}$ is computed by $\mathcal{C}$ on $\{(p^{(1)}_{i},\delta^{(1)}_{i}),\dots,(p^{(j-1)}_{i},\delta^{(j-1)}_{i})\}$ and error parameter $\varepsilon/40$ , we have that $\mathsf{dist}(p^{(j^{\prime})}_{i},x^{(j)}_{i})\leq(1+\nicefrac{{\varepsilon}}% {{40}})\delta^{(j^{\prime})}_{i}$ , for $j^{\prime}<j$ . Hence, $S_{i}$ is $(\mathcal{C},\nicefrac{{\varepsilon}}{{20}})$ -algorithmic scattering.

Now we bound that the radii of sequence $S_{i},i\in[k]$ . Towards this, we partition $S_{i}$ into $S^{n}_{i}$ and $S^{f}_{i}$ , based on a partitioning of $Q_{i}$ , as follows. We say a request $(p^{(j)}_{i},\delta^{(j)}_{i})\in Q_{i}$ belongs to $Q^{n}_{i}$ if $p^{(j)}_{i}$ was sampled when the If condition was satisfied (in Line 12), otherwise it belongs to $Q_{i}^{f}$ , which corresponds to the Else condition (in Line 15). Correspondingly, $(x^{(j)}_{i},p^{(j)}_{i},\delta^{(j)}_{i})\in S^{n}_{i}$ if $(p^{(j)}_{i},\delta^{(j)}_{i})\in Q^{n}_{i}$ and $(x^{(j)}_{i},p^{(j)}_{i},\delta^{(j)}_{i})\in S^{f}_{i}$ if $(p^{(j)}_{i},\delta^{(j)}_{i})\in Q^{f}_{i}$ . We bound the aspect ratio of each part, $S^{n}_{i}$ and $S^{f}_{i}$ , separately. For $(x^{(j)}_{i},p^{(j)}_{i},\delta^{(j)}_{i})\in S_{i}^{n}$ , we have $r\leq\delta^{(j)}_{i}\leq 8r/\varepsilon$ and hence, the radii of triples in $S^{n}_{i}$ lie in interval $[r,8r/\varepsilon].$ Now consider $(x^{(j)}_{i},p^{(j)}_{i},\delta^{(j)}_{i})\in S_{i}^{f}$ . Recall that $X^{(j)}$ is the solution maintained by the algorithm when $(p^{(j)}_{i},\delta^{(j)}_{i})$ is added to $Q_{i}$ . Then, note that $\mathsf{dist}_{r^{\prime}}(p^{(j)}_{i},X^{(j)})>\varepsilon u(p)/1000k$ (see Line 14), and hence, we have $\mathsf{dist}(p^{(j)}_{i},X^{(j)})>\varepsilon u(p)/1000k$ . The following claim, whose proof is similar to [1], shows that the radii of requests in $S^{f}_{i}$ are also bounded, finishing the proof of the lemma.

Claim 13.

Consider requests $(p,\delta_{p}),(p^{\prime},\delta_{p^{\prime}})$ added (in any order) to $Q_{i}$ in Line 18 of Algorithm 1 such that $(p,\delta_{p}),(p^{\prime},\delta_{p^{\prime}})\in Q^{f}_{i}$ . If $\delta_{p^{\prime}}<\nicefrac{{\varepsilon^{2}\delta_{p}}}{{10^{5}k}}$ , then the algorithm fails in Line 19 upon making second of the two requests.

Proof.

Suppose, for the sake of contradiction, the algorithm does not fail and finds a center $x_{i}$ such that $\mathsf{dist}_{(}p,x_{i})\leq(1+\varepsilon/40)\delta_{p}$ and $\mathsf{dist}(p^{\prime},x_{i})\leq(1+\varepsilon/40)\delta_{p^{\prime}}$ . Thus, $\mathsf{dist}(p,p^{\prime})\leq\mathsf{dist}(p,x_{i})+\mathsf{dist}(p^{\prime}% ,x_{i})\leq(1+\varepsilon/40)(\delta_{p}+\delta_{p^{\prime}})$ .

Therefore, we have

\mathsf{dist}(p,X)\leq\mathsf{dist}(p,p^{\prime})+\mathsf{dist}(p^{\prime},X)% \leq(1+\varepsilon/40)(\delta_{p}+\delta_{p^{\prime}})+3.1u(p^{\prime}),

using Observation 11. Let $X$ be the center maintained by the algorithm when the request $(p,\delta_{p})$ is added to $Q_{i}$ . Then, we have

\delta_{p}=\frac{\mathsf{dist}(p,X)}{(1+\varepsilon/12)},

(1)

due to Line 18. Similarly, let $X^{\prime}$ be the center maintained by the algorithm when request $(p^{\prime},\delta_{p^{\prime}})$ is added to $Q_{i}$ . Then, since $(p^{\prime},\delta_{p^{\prime}})\in Q^{f}_{i}$ , we have that $u(p^{\prime})\leq 900\mathsf{dist}(p^{\prime},X^{\prime})/\varepsilon=1000k% \delta_{p^{\prime}}/\varepsilon$ , using $\delta_{p^{\prime}}=\frac{\mathsf{dist}(p^{\prime},X^{\prime})}{(1+\varepsilon% /12)}$ . Therefore, using $\delta_{p^{\prime}}<\nicefrac{{\varepsilon^{2}\delta_{p}}}{{10^{5}k}}$ ,

	$\displaystyle\mathsf{dist}(p,X)$	$\displaystyle\leq(1+\nicefrac{{\varepsilon}}{{40}})(\delta_{p}+\delta_{p^{% \prime}})+{3000k\delta_{p^{\prime}}}/{\varepsilon}\leq(1+\nicefrac{{% \varepsilon}}{{40}})\delta_{p}+{3200k\delta_{p^{\prime}}}/{\varepsilon}$
		$\displaystyle\leq(1+\nicefrac{{\varepsilon}}{{40}}+\nicefrac{{\varepsilon}}{{2% 5}})\delta_{p}<(1+\nicefrac{{\varepsilon}}{{12}})\delta_{p}$

This means $\delta_{p}>\frac{\mathsf{dist}(p,X)}{1+\varepsilon/12}$ , contradicting (1). $\hfill\vartriangleleft$ $\hfill\blacktriangleleft$ Now we are ready to finish the proof of Lemma 7.

Proof of Lemma 7.

We apply Corollary 6 to $S_{i}$ and note that the radii in $S_{i}$ lie in $[r,8r/\varepsilon]\cup[r_{min},\frac{10^{5}k}{\varepsilon^{2}}r_{min}]$ , where $r_{min}$ is the smallest radii in $S_{i}$ that is larger than $8r/\varepsilon$ , due to Lemma 12. This implies that the length of sequence $S_{i}$ is bounded by $O(\lambda(\nicefrac{{\varepsilon}}{{40}})\frac{(\log(\nicefrac{{k}}{{% \varepsilon}}))}{\varepsilon})$ . Since in each iteration the algorithm adds one request to some $Q_{i}$ , the total number of iterations is bounded by $O(\frac{k}{\varepsilon}\lambda(\nicefrac{{\varepsilon}}{{40}})(\log(\nicefrac{% {k}}{{\varepsilon}}))$ . $\hfill\blacktriangleleft$

3.2.2 Bounding success probability

The goal of this subsection is to prove Lemma 8, i.e., give a lower bound on the success probability of the algorithm. To this end, we first introduce the following notion.

Definition 14 (Consistency).

Consider a fixed hypothetical optimal solution $O=(o_{1},\cdots,o_{k})$ . We say that the current state of execution (specified by $(X,Q_{1},\cdots,Q_{k})$ ) of Algorithm 1 is consistent with $O$ if for any request $(p,\delta)\in Q_{i},i\in[k]$ , we have $\mathsf{dist}(p,o_{i})\leq\delta$ .

Note that, Lemma 11 implies that the initial set of requests (line 4) are feasible. Since the balls ${\sf ball}(p^{(i)},u(p^{(i)})),i\in[k^{\prime}]$ are disjoint, we can relabel the optimum centers $O=\{o_{1},\dots,o_{k}\}$ so that $\mathsf{dist}(p^{(i)},o_{i})\leq u(p^{(i)})$ . Thus, Lemma 11 implies that the initial state of the algorithm as computed in lines 1 to 6 is consistent with a fixed optimal solution $O$ which is fixed henceforth. To prove Lemma 8, we will inductively argue that the state of the algorithm remains consistent with $O$ – note that the base case is already shown. Most of this subsection is devoted to show the inductive step, i.e., to show that, given a consistent state at the start of an iteration, there is a good probability that the state of the algorithm at the end of the iteration is also consistent (cf. Lemma 22).

To this end, we introduce the following definitions w.r.t. the current solution $X$ .

Definition 15 (Contribution and Witness).

For any set $S\subseteq P$ , we use $C_{S}\coloneqq\sum_{p\in S}\mathsf{dist}_{r^{\prime}}(p,X)$ to denote the contribution of the set $S$ to the cost of the current solution.

We say that a point $p\in P$ is an $\varepsilon/3$ -witness (or simply, a witness) w.r.t. the solution $X$ if it satisfies $\mathsf{dist}_{(1+\nicefrac{{\varepsilon}}{{3}})r}(p,X)>(1+\nicefrac{{% \varepsilon}}{{3}})\cdot\mathsf{dist}_{r}(p,O)$ .

The following claim can be proved by a simple averaging argument.

Claim 16 ( $\spadesuit$ ).

$C_{W}\geq\frac{\varepsilon C_{P}}{10}$ .

Next, we introduce several different classifications of witnesses.

Definition 17 (Different subsets of witnesses).

For each $x_{j}\in X$ , let $W_{j}$ denote the set of witnesses for which $x_{j}$ is a nearest center in $X$ (breaking ties arbitrarily). Then, $W_{j,{\sf near}}\coloneqq\left\{p\in W_{j}:\mathsf{dist}(p,x_{j})\leq\nicefrac% {{8r}}{{\varepsilon}}\right\}$ , and $W_{j,{\sf far}}\coloneqq W_{j}\setminus W_{j,{\sf near}}$ . Further, let $W_{\sf near}\coloneqq\bigcup_{j\in[k]}W_{j,{\sf near}}$ , and $W_{\sf far}\coloneqq\bigcup_{j\in[k]}W_{j,{\sf far}}$ . We will refer to a witness in $W_{\sf near}$ as a nearby witness and a witness in $W_{\sf far}$ as a faraway witness.

Now, we consider two different cases regarding the behavior of the algorithm.

Case 1: $C_{W_{\sf near}}\geq\frac{\varepsilon}{100}C_{P}$ .

In this case, when we sample a point from $N\coloneqq\{p\in P:\mathsf{dist}(p,X)\leq 8r/\varepsilon\}$ proportional to their $\mathsf{dist}_{r^{\prime}}(\cdot,X)$ values, the probability of sampling a nearby witness is at $\frac{\varepsilon}{100}$ . This will correspond to the “good event”. We prove this formally in the following lemma.

Lemma 18 (Nearby witness lemma).

Suppose the current solution $X$ at the start of an iteration satisfies $\mathsf{cost}_{r^{\prime}}(P,X)>(1+\varepsilon)\cdot\mathcal{G}$ . Further, suppose $C_{W_{\sf near}}\geq\frac{\varepsilon}{100}C_{P}$ . Then, with probability at least $\frac{\varepsilon}{200k}$ , the point $p\in P$ , the index $i\in[k]$ , and value $\delta_{p}$ defined in the iteration satisfy the following properties.

1.

$o_{i}\in O$ is the closest center to $p\in P$ , i.e., $\mathsf{dist}(p,o_{i})=\mathsf{dist}(p,O)$ ,
2.

$p\in W_{\sf near}$ , i.e., (i) $\mathsf{dist}_{r^{\prime}(p,X)}>(1+\nicefrac{{\varepsilon}}{{3}})\mathsf{dist}% _{r}(p,o_{i})$ , and (ii) $\mathsf{dist}(p,X)\leq\frac{8r}{\varepsilon}$ .
3.

$\mathsf{dist}(p,o_{i})<\frac{\mathsf{dist}(p,X)}{1+\nicefrac{{\varepsilon}}{{1% 2}}}=:\delta_{p}\leq\frac{8r}{\varepsilon}$ .

Proof.

First, in line 10 with probability $1/2$ , we correctly move to the “nearby witness” (if) case of line 10. We condition on this event. Next, note that $W_{\sf near}\subseteq N$ , and $C_{W_{\sf near}}\geq\frac{\varepsilon}{100}C_{P}\geq\frac{\varepsilon}{100}C_{N}$ , where the first inequality is due to the case assumption. Therefore, in line 12, the point $p$ sampled from $N$ , will belong to $W_{\sf near}$ with probability at least $\frac{\varepsilon}{100}$ . Let $i\in[k]$ denote the index such that $o_{i}\in O$ is the closest center in the optimal solution $O$ , and we correctly guess the index $i$ in line 17. Note that the probability of the algorithm making the “correct” random choices is at least $\frac{1}{2}\cdot\frac{\varepsilon}{100}\cdot\frac{1}{k}=\frac{\varepsilon}{200k}$ .

We condition on the said events. Since $p$ is a witness, we know that $\mathsf{dist}_{r^{\prime}}(p,X)>(1+\nicefrac{{\varepsilon}}{{3}})\cdot\mathsf{% dist}_{r}(p,o_{i})$ . We first observe that $\mathsf{dist}_{r^{\prime}}(p,X)$ must be positive, which implies that $\mathsf{dist}(p,X)>r^{\prime}=(1+\nicefrac{{\varepsilon}}{{3}})r$ . Now, we consider two cases based on the value of $\mathsf{dist}(p,O)$ .

If $\mathsf{dist}(p,o_{i})<r$ , then $\mathsf{dist}_{r}(p,o_{i})=0$ , in which case,

\mathsf{dist}(p,o_{i})<r\leq\frac{r^{\prime}}{1+\nicefrac{{\varepsilon}}{{12}}% }\leq\frac{\mathsf{dist}(p,X)}{1+\nicefrac{{\varepsilon}}{{12}}}

(2)

Otherwise, $\mathsf{dist}(p,o_{i})\geq r$ , in which case $\mathsf{dist}_{r}(p,o_{i})=\mathsf{dist}(p,o_{i})-r$ . Then, consider

	$\displaystyle\mathsf{dist}(p,X)-(1+\tfrac{\varepsilon}{3})r=\mathsf{dist}_{r^{% \prime}}(p,X)>(1+\tfrac{\varepsilon}{3})\cdot\mathsf{dist}_{r}(p,o_{i})=(1+% \tfrac{\varepsilon}{3})(\mathsf{dist}(p,o_{i})-r)$
$\displaystyle\implies$	$\displaystyle\mathsf{dist}(p,X)-(1+\tfrac{\varepsilon}{3})r>(1+\tfrac{% \varepsilon}{3})\cdot\mathsf{dist}(p,o_{i})-(1+\tfrac{\varepsilon}{3})r$
$\displaystyle\implies$	$\displaystyle\mathsf{dist}(p,o_{i})<\frac{\mathsf{dist}(p,X)}{1+\nicefrac{{% \varepsilon}}{{3}}}\leq\frac{\mathsf{dist}(p,X)}{1+\nicefrac{{\varepsilon}}{{1% 2}}}$	(3)

Thus, regardless of the value of $\mathsf{dist}(p,o_{i})$ , we have established the third item, hence completing the proof of the lemma. $\hfill\blacktriangleleft$

Case 2: $C_{W_{\sf near}}<\frac{\varepsilon}{100}C_{P}$ .

In this case, most of contribution of witnesses is coming from “faraway witnesses”. In this case, the “correct choice” corresponds to the case when we sample points from the set $A=\left\{p\in P:\mathsf{dist}_{r^{\prime}}(p,X)>\frac{\varepsilon}{1000k}\cdot u% (p)\right\}$ as defined in line 14. In this case, we will show that with good probability, the sampled point is a “faraway witness”. Specifically, we show the following lemma.

Lemma 19 (Faraway witness lemma).

Suppose the current solution $X$ at the start of an iteration satisfies $\mathsf{cost}_{r^{\prime}}(P,X)>(1+\varepsilon)\cdot\mathcal{G}$ . Further, suppose $C_{W_{\sf near}}<\frac{\varepsilon}{100}C_{P}$ . Then, with probability at least $\frac{\varepsilon}{16k}$ , the point $p\in P$ , the index $i\in[k]$ , and value $\delta_{p}$ defined in the iteration satisfy the following properties.

1.

$o_{i}\in O$ is the closest center to $p$ , i.e., $\mathsf{dist}(p,o_{i})=\mathsf{dist}(p,O)$ ,
2.

$p\in W_{\sf far}$ , i.e., (i) $\mathsf{dist}_{r^{\prime}(p,X)}>(1+\nicefrac{{\varepsilon}}{{3}})\mathsf{dist}% _{r}(p,o_{i})$ , and (ii) $\mathsf{dist}(p,X)>\frac{8r}{\varepsilon}$ ,
3.

$\mathsf{dist}_{r^{\prime}}(p,X)>\frac{\varepsilon}{1000k}u(p)$ , and
4.

$\mathsf{dist}(p,o_{i})<\frac{\mathsf{dist}(p,X)}{1+\nicefrac{{\varepsilon}}{{1% 2}}}=:\delta_{p}\leq\frac{8r}{\varepsilon}$ .

Proof.

First, in line 10 with probability $1/2$ , we correctly move to the “faraway witness” (else) case of line 13. We condition on this event. Now, by combining Algorithm 16 and the case assumption we obtain,

C_{W_{\sf far}}=C_{W}-C_{W_{\sf near}}\geq C_{P}\cdot\left(\tfrac{\varepsilon}% {10}-\tfrac{\varepsilon}{100}\right)=\tfrac{\varepsilon}{9}C_{P}.

(4)

Next, let $H\coloneqq\left\{j\in[k]:C_{W_{j,{\sf far}}}\geq\frac{\varepsilon C_{P}}{100k}\right\}$ . It follows that,

	$\displaystyle\sum_{j\in[k]\setminus H}C_{W_{j,{\sf far}}}$	$\displaystyle\leq k\cdot\frac{\varepsilon C_{P}}{100k}$
	$\displaystyle\implies\sum_{j\in H}C_{W_{j,{\sf far}}}$	$\displaystyle\geq C_{W_{\sf far}}-\sum_{j\in[k]\setminus H}C_{W_{j,{\sf far}}}% \geq\frac{\varepsilon C_{P}}{9}-\frac{\varepsilon C_{P}}{100}\geq\frac{% \varepsilon C_{P}}{8}$		(5)

Fix a $j\in H$ , and let us index the points in $W_{j,{\sf far}}=\left\{z_{1},z_{2},\ldots,z_{\ell}\right\}$ in the non-decreasing order of their distances $\mathsf{dist}(z,x_{j})$ (and equivalently, $\mathsf{dist}_{r}(z,x_{j})$ ). First, we state the following simple consequences of various definitions for future reference.

Observation 20 ( $\spadesuit$ ).

For each $z\in W_{j,{\sf far}}$ , the following bounds hold.

1.

$\mathsf{dist}(z,x_{j})\geq\frac{8r}{\varepsilon}$ ,
2.

$\mathsf{dist}(z,O)>(1+\frac{\varepsilon}{3})\cdot\mathsf{dist}(z,x_{j})$
3.

$\mathsf{dist}_{r^{\prime}}(z,x_{j})\geq\frac{6r}{\varepsilon}$ , and
4.

$\mathsf{dist}_{r}(z,x_{j})\leq\mathsf{dist}(z,x_{j})\leq(1+\frac{\varepsilon}{% 5})\cdot\mathsf{dist}_{r^{\prime}}(z,x_{j})\leq(1+\frac{\varepsilon}{5})\cdot% \mathsf{dist}_{r}(z,x_{j})$ .

Let us return to the points in $W_{j,{\sf far}}=\left\{z_{1},z_{2},\ldots,z_{\ell}\right\}$ . Let $q\in[\ell]$ denote the minimum index such that, the contribution of the set $W^{-}_{j,{\sf far}}=\left\{z_{1},z_{2},\ldots,z_{q}\right\}$ , is at least $\frac{C_{W_{j,{\sf far}}}}{2}$ . Note that by a simple argument, this implies that the contribution of the set $W^{+}_{j,{\sf far}}=W_{j,{\sf far}}\setminus W^{-}_{j,{\sf far}}$ is also at least $\frac{C_{W_{j,{\sf far}}}}{3}$ (see, e.g., Lemma 7.20 in [21]). Hence, we have the following lower bounds on the contribution of both the sets, by recalling that $j\in H$ .

C_{W^{-}_{j,{\sf far}}}\geq\frac{\varepsilon\,C_{P}}{200k},\qquad C_{W^{+}_{j,% {\sf far}}}\geq\frac{\varepsilon\,C_{P}}{300k}

(6)

Next, we first prove the following technical claim.

Claim 21.

Let $j\in H$ . For all $p\in W^{+}_{j,{\sf far}}$ , it holds that $u(p)\leq\frac{900k\mathsf{dist}(p,x_{j})}{\varepsilon}$ . Therefore, $W^{+}_{j,{\sf far}}\subseteq A$ .

Proof.

For this proof, we use the following shorthand: $W^{+}\coloneqq W^{+}_{j,{\sf far}}$ , and $W^{-}\coloneqq W^{-}_{j,{\sf far}}$ . Now, fix an arbitrary point $p\in W^{+}$ . For any $q\in W^{-}$ , $\mathsf{dist}(p,x_{j})\geq\mathsf{dist}(q,x_{j})$ , which implies that

\mathsf{dist}(p,q)\leq\mathsf{dist}(p,x_{j})+\mathsf{dist}(q,x_{j})\leq 2\cdot% \mathsf{dist}(p,x_{j})\leq 2(1+\tfrac{\varepsilon}{5})\cdot\mathsf{dist}_{r^{% \prime}}(p,x_{j})\leq 4\cdot\mathsf{dist}_{r^{\prime}}(p,x_{j})

(7)

Here, we use the property 4 from Observation 20 in the third inequality in the above. On the other hand, note that,

\displaystyle\frac{\varepsilon\,{\sf OPT}_{r}}{200k}\leq\frac{\varepsilon\,C_{% P}}{200k}\leq C_{W^{-}}=\sum_{q\in W^{-}}\mathsf{dist}_{r^{\prime}}(q,x_{j})% \leq\mathsf{dist}_{r^{\prime}}(p,x_{j})\cdot|W^{-}|

(8)

Then, if we set $\alpha=12\mathsf{dist}_{r^{\prime}}(p,x_{j})$ , from (7), we obtain that $W^{-}\subseteq{\sf ball}(p,\alpha/3)$ . Now, combining this with (8), we obtain that,

\displaystyle|{\sf ball}(p,\alpha/3)|\geq|W^{-}|\geq\frac{\varepsilon% \leavevmode\nobreak\ {\sf OPT}_{r}}{300k\cdot\mathsf{dist}_{r^{\prime}}(p,x_{j% })}\geq\frac{\varepsilon\leavevmode\nobreak\ {\sf OPT}_{r}}{25k\alpha}=\frac{% \varepsilon\leavevmode\nobreak\ {\sf OPT}_{r}}{75k(\alpha/3)}

(9)

Hence, we have that $|{\sf ball}(p,\nicefrac{{75k\alpha}}{{3\varepsilon}})|\geq\frac{\varepsilon% \leavevmode\nobreak\ {\sf OPT}_{r}}{75k(\alpha/3)}$ . Using $\mathsf{dist}(p,x_{j})\geq\nicefrac{{8r}}{{\varepsilon}}$ from Observation 20 and the fact $\mathsf{dist}_{r}(p,x_{j})\geq 5\mathsf{dist}(p,x_{j})/6$ , we have $\frac{75k\alpha}{3\varepsilon}=\frac{300k\,\mathsf{dist}_{r^{\prime}}(p,x_{j})% }{\varepsilon}>r$ . Therefore, $u(p)\leq\frac{900k\,\mathsf{dist}_{r^{\prime}}(p,x_{j})}{\varepsilon}\leq\frac% {900k\,\mathsf{dist}(p,x_{j})}{\varepsilon}$ , as desired. $\hfill\vartriangleleft$

Recall from (5) that $C_{W_{\sf far}\cap A}\geq\sum_{j\in H}C_{W^{+}_{j,{\sf far}}}\geq\frac{% \varepsilon\,C_{P}}{8}\geq\frac{\varepsilon\,C_{A}}{8}$ , therefore, when we sample a point from $A$ , the probability that the sampled point $p$ belongs to $\bigcup_{j\in H}W^{+}_{j,{\sf far}}$ is at least $\frac{\varepsilon}{8}$ . Now, we condition on this event. Let $o_{i}\in O$ be the nearest center to $p$ , and in line 17, the probability that we sample the correct index is $\frac{1}{k}$ . Thus, the total probability of the algorithm making the “correct choices” in this case is at least $\frac{1}{2}\cdot\frac{\varepsilon}{8}\cdot\frac{1}{k}=\frac{\varepsilon}{16k}$ . We condition on these choices. Note that, item 1 is thus satisfied due to the correct sampling of $i$ , item 2 is satisfied due $p\in\bigcup_{j\in H}W^{+}_{j,{\sf far}}\subseteq W_{\sf far}\subseteq W$ , and item 3 is satisfied since $p\in A$ by construction. Thus, we are only left with showing item 4, to which end, we consider different cases for the distance between $p$ and its closest optimal center, $o_{i}$ .

If $\mathsf{dist}(p,o_{i})<\frac{6r}{\varepsilon}$ , then since $\mathsf{dist}(p,X)\geq\frac{8r}{\varepsilon}$ , it easily follows that,

\mathsf{dist}(p,o_{i})<\tfrac{3}{4}\cdot\mathsf{dist}(p,X)\leq\frac{\mathsf{% dist}(p,X)}{1+\nicefrac{{\varepsilon}}{{12}}}

(10)

Otherwise, if $\mathsf{dist}(p,o_{i})\geq\frac{6r}{\varepsilon}$ , then similar item 4 of Observation 20, we can show that,

\mathsf{dist}_{r}(p,o_{i})<\mathsf{dist}(p,o_{i})\leq(1+\tfrac{\varepsilon}{3}% )\cdot\mathsf{dist}_{r}(p,o_{i})

(11)

However, since $p$ is an $\varepsilon/3$ -witness, it follows that, $\mathsf{dist}_{r^{\prime}}(p,X)>(1+\frac{\varepsilon}{3})\cdot\mathsf{dist}_{r% }(p,O)$ . Therefore, we obtain that,

\displaystyle\mathsf{dist}(p,x_{j})\geq\mathsf{dist}_{r^{\prime}}(p,x_{j})>(1+% \tfrac{\varepsilon}{3})\cdot\mathsf{dist}_{r}(p,o_{i})

\displaystyle\geq\frac{1+\nicefrac{{\varepsilon}}{{3}}}{1+\nicefrac{{% \varepsilon}}{{5}}}\cdot\mathsf{dist}(p,o_{i})\geq(1+\tfrac{\varepsilon}{12})% \cdot\mathsf{dist}(p,o_{i})

(12)

Thus, in each of the sub-cases, in (10) and (12), we have shown that $\mathsf{dist}(p,o_{i})<\frac{\mathsf{dist}(p,X)}{1+\nicefrac{{\varepsilon}}{{1% 2}}}$ , thus completing the proof of the lemma. $\hfill\blacktriangleleft$

Lemma 18 and Lemma 19 can be combined in a straightforward way to obtain the following lemma completing the inductive step.

Lemma 22.

Consider an iteration of the algorithm such that the state of execution $(X,Q_{1},\ldots,Q_{k})$ at the start of the iteration is consistent with a fixed optimal solution $O$ , and further $\mathsf{cost}_{r^{\prime}}(P,X)>(1+\varepsilon)\cdot\mathcal{G}$ . Then, with probability at least $\frac{\varepsilon}{200k}$ , the state of the algorithm at the end of the iteration $(X^{\prime},Q^{\prime}_{1},Q^{\prime}_{2},\ldots,Q^{\prime}_{k})$ is also consistent with $O$ .

Proof.

Consider the scenario described in the premise of the lemma. Then, the solution $X$ at the start of the iteration either satisfies that $C_{W_{\sf near}}\geq\frac{\varepsilon}{100}C_{P}$ (nearby witness case), or $C_{W_{\sf near}}\geq\frac{\varepsilon}{100}C_{P}$ (faraway witness case). Then, Lemmas 18 and 19; along with the correctness of $\mathcal{C}$ , together imply that, conditioned on the respective case assumption, the probability that the state of the algorithm is consistent with $O$ is at least $\frac{\varepsilon}{200k}$ . ⁹⁹9Note that this probability also accounts for the result of the coin toss in line 10. $\hfill\blacktriangleleft$ Armed with Lemma 22, it is easy to conclude the proof of Lemma 8.

Proof of Lemma 8.

As argued initially, the state of the algorithm at line 6 is consistent with the optimal solution $O$ . Then, Lemma 22 implies that, for any $\ell\geq 1$ , if the algorithm runs for $\ell$ iterations, then with probability at least $\left(\frac{\varepsilon}{200k}\right)^{\ell}$ , the state of the algorithm remains consistent. Further, note that as long as the state of the algorithm remains consistent with $O$ , then the algorithm cannot fail. Finally, Lemma 7 implies that the algorithm terminates within $O(\frac{k}{\varepsilon}\lambda(\frac{\varepsilon}{40})\log(\frac{k}{40}))$ iterations. Therefore, the probability that the algorithm terminates without failure – i.e., by successfully breaking the while loop by finding a solution $X$ satisfying $\mathsf{cost}_{r^{\prime}}(P,X)\leq(1+\varepsilon){\sf OPT}_{r}$ , is at least $\left(\frac{\varepsilon}{k}\right)^{O(\frac{k}{\varepsilon}\lambda(\frac{% \varepsilon}{40})\log(\frac{k}{40}))}=\exp\left(-O\left(\frac{k}{\varepsilon}% \log(\frac{k}{\varepsilon})\lambda(\frac{\varepsilon}{40})\right)\right)$ . $\hfill\blacktriangleleft$

4 Extensions of the Bicriteria FPT-AS

Fomin et al. [23] defined a generalization of Hybrid $k$ -Clustering, which they call Hybrid $(k,z)$ -clustering, wherein the objective is $\sum_{p\in P}(\mathsf{dist}_{r}(p,X))^{z}$ , for fixed $z\geq 1$ , which simultaneously generalizes $(k,z)$ -Clustering and $k$ -Center. They generalized their algorithm for $z=2$ , i.e., Hybrid $k$ -Means, but left the possibility of extending to an arbitrary value of $z$ conditional on the existence of a certain kind of sampling algorithm. In this paper, we consider a much more general Hybrid Norm $k$ -Clustering problem that captures all $(k,z)$ -Clustering problems, and much more. Here, the objective is to find a set $X\subseteq\mathbb{F}$ that minimizes $f(\mathbf{d}_{r}(P,X))$ , where $\mathbf{d}_{r}(P,X)=(\mathsf{dist}_{r}(p_{1},X),\mathsf{dist}_{r}(p_{2},X),% \ldots,\mathsf{dist}_{r}(p_{n},X))$ is the vector of $r$ -distances to the solution $X$ , and $f:\mathbb{R}^{n}\to\mathbb{R}$ is a monotone norm¹⁰¹⁰10 $f:\mathbb{R}^{n}\to\mathbb{R}$ is a norm if it satisfies following properties for any $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$ and any $\lambda\in\mathbf{R}$ , (i) $f(\mathbf{x})=0$ iff $\mathbf{x}=\mathbf{0}$ , (ii) $f(\mathbf{x}+\mathbf{y})\leq f(\mathbf{x})+f(\mathbf{y})$ , (iii) $f(\lambda\mathbf{x})=|\lambda|f(\mathbf{x})$ ; furthermore, $f$ is monotone if $f(\mathbf{x})\leq f(\mathbf{y})$ whenever $\mathbf{x}\leq\mathbf{y}$ , where $\leq$ denotes point-wise inequality. – we refer the reader to [1] for a detailed background on norms and related notions.

Algorithm 1 and its analysis can be extended to the general norm objective following the approach of [1]. Here, we only sketch the modifications required to the algorithm and its proof, since this is not the main focus of this work.

The initial upper bounds $u(p)$ can be found in a similar manner. The while loop runs as long as the solution $X$ in hand satisfies that $f(\mathbf{d}_{r^{\prime}}(P,X))>(1+\nicefrac{{\varepsilon}}{{3}})\cdot{\sf OPT% }_{r}$ , where $\mathbf{d}_{r^{\prime}}$ denotes the vector of distances $(\mathsf{dist}_{r^{\prime}}(p,X))_{p\in X}$ , and $r^{\prime}=(1+\nicefrac{{\varepsilon}}{{3}})r$ . If this is the case, then the first step is to compute¹¹¹¹11Actually, it is sufficient to compute an approximate subgradient, as done in [1]. a subgradient of $f$ at $\mathbf{d}_{r^{\prime}}$ , which is, loosely speaking, a weight function $w:P\to\mathbb{R}_{\geq 0}$ , such that it suffices to focus the attention in the current iteration on ${\sf wcost}_{r^{\prime}}(P,X)\coloneqq\sum_{p\in P}w(p)\mathsf{dist}_{r}(p,X)$ that satisfies ${\sf wcost}_{r^{\prime}}(P,X)=f(\mathbf{d}_{r^{\prime}}(P,X))>(1+\nicefrac{{% \varepsilon}}{{3}})\cdot{\sf OPT}_{r}$ . Our algorithm proceeds in a similar fashion, except that whenever points are sampled from the set $N$ (in line 12) or set $A$ (in line 15), the probability of sampling a point $p$ is proportional to $w(p)\cdot\mathsf{dist}_{r}(p,X)$ . The rest of the algorithm remains unchanged.

There are a few minor modifications required in the analysis – mainly in Section 3.2.2. First, while the definition of an $(\varepsilon/3)$ -witness (or simply a witness) remains unchanged, we redefine the contribution of a subset $S\subseteq P$ to be $C_{S}\coloneqq\sum_{p\in S}w(p)\cdot\mathsf{dist}_{r}(p,X)$ . The nearby and faraway witness cases are then considered exactly as in Section 3.2.2. The proof of the analogue of Lemma 18 goes through without any modifications; whereas we need to be slightly more careful in the proof of the analogue of Lemma 19. Here, in inequalities (8 and 9) we need to take the weighted distances into account and relate $C_{P}$ to $f(\mathbf{d}_{r^{\prime}}(P,X))$ , which requires a slight worsening of constants. With these minor changes in place, we can conclude that the state of the algorithm after $\ell$ iterations is consistent with a fixed optimal solution $O$ with probability at least $\Omega(\left(\frac{\varepsilon}{k}\right))^{\ell}$ . The analysis for bounding the number of iterations remains unchanged, and hence we obtain an FPT-AS with a similar running time, modulo the constants hidden in the big-Oh notation. We omit the details.

5 Coreset

In this section, we design a coreset for Hybrid $k$ -Clustering in doubling metric of bounded dimension. More specifically, we prove the following (restated for convenience). See 3

Proof.

A formal description of our algorithm can be found in the full version of the paper. Here, we provide an overview of the overview, which is based on grid construction approach of [26, 2]. Let $T\subseteq P\cup\mathbb{F}$ be an approximate solution that satisfies the following properties: (i) $|T|\leq 2^{O(d)}k$ , and (ii) $\mathsf{cost}_{r}(P,T)\leq 36\cdot{\sf OPT}_{r}$ ¹²¹²12Note the set $T$ is a bicriteria solution, but in a different sense, since it approximates the size and the cost while using $r$ -distances.. For each $t_{i}\in T$ , consider the balls $B^{j}_{i}={\sf ball}(t_{i},2^{j}R)$ , for $j\in\{0,1,\dots,2\log\lceil\alpha n\rceil\}$ . Note that, since $\mathsf{dist}(p,T)\leq\mathsf{cost}(P,T)=\alpha n\cdot R$ , we have that $p$ lies in some ball $B^{j}_{i}$ , for $i\in[\gamma k]$ and $j\in\{0,1,\dots,2\log\lceil\alpha n\rceil\}$ .

The idea is to decompose each $B^{j}_{i}$ into smaller balls each of radius $\frac{\varepsilon 2^{j}R}{4\alpha}$ , and associate each point $p\in P$ to a unique smallest ball containing $p$ , breaking ties arbitrary. We say a small ball $b$ is non-empty if there is a point in $P$ associated with $b$ . Next, for each non-empty ball $b$ , pick an arbitrary point $p$ associated with $b$ and add $p$ to $P^{\prime}$ with weight $w(p)$ equal to the total number of points associated with $b$ ; we call such a point $p$ as the representative of points associated with $b$ .

To bound the size of $P^{\prime}$ , note that, in doubling metric of dimension $d$ , a unit ball can be covered by $2^{O(d\log(1/\varepsilon))}$ balls, each of radius $\varepsilon$ . Hence, we have $|P^{\prime}|=O(2^{O(d\log(1/\varepsilon))}\gamma k\log(\alpha n))$ .

Recall that, for $X\subseteq\mathbb{F},|X|\leq k$ , we define the weighted cost of $X$ with respect to $(P^{\prime},\{w(p^{\prime})\}_{p^{\prime}\in P^{\prime}})$ as ${\sf wcost}_{r}(P^{\prime},X)=\sum_{p^{\prime}\in P}w(p^{\prime})d_{r}(p^{% \prime},X)$ . Now we show that the cost of $X$ with respect to $(P^{\prime},\{w(p^{\prime})\}_{p^{\prime}\in P^{\prime}})$ approximately preserves the cost of $X$ with respect to $P$ . Consider a point $p\in P$ and let $p^{\prime}\in P^{\prime}$ be its representative in $P^{\prime}$ . Now, the contribution of $p$ towards $\mathsf{cost}_{r}(P,X)$ is $\mathsf{dist}_{r}(p,X)$ . On the other hand, its contribution towards ${\sf wcost}_{r}(P^{\prime},X)$ is $\mathsf{dist}_{r}(p^{\prime},X)$ . Hence,

|{\sf wcost}_{r}(P^{\prime},X)-\mathsf{cost}_{r}(P,X)|\leq\sum_{p\in P}|% \mathsf{dist}_{r}(p,X)-\mathsf{dist}_{r}(p^{\prime},X)|.

Now if $p\in\bigcup_{i\in\gamma k}B^{0}_{i}$ , then $\mathsf{dist}(p,X)-\frac{\varepsilon R}{4\alpha}\leq\mathsf{dist}(p^{\prime},X% )\leq\mathsf{dist}(p,X)+\frac{\varepsilon R}{4\alpha}$ . Hence,

\max\{\mathsf{dist}(p,X)-\nicefrac{{\varepsilon R}}{{4\alpha}}-r,0\}\leq% \mathsf{dist}_{r}(p^{\prime},X)\leq\max\{\mathsf{dist}(p,X)+\nicefrac{{% \varepsilon R}}{{4\alpha}}-r,0\}

Therefore, $\mathsf{dist}_{r}(p,X)-\nicefrac{{\varepsilon R}}{{4\alpha}}\leq\mathsf{dist}_% {r}(p^{\prime},X)\leq\mathsf{dist}_{r}(p,X)+\nicefrac{{\varepsilon R}}{{4% \alpha}}$ . Hence, we have

\sum_{p\in P_{0}}|\mathsf{dist}_{r}(p,X)-\mathsf{dist}_{r}(p^{\prime},X)|\leq% \frac{\varepsilon Rn}{4\alpha}\leq\frac{\varepsilon{\sf OPT}_{r}}{2}\leq\frac{% \varepsilon\mathsf{cost}_{r}(P,X)}{2}.

Now, suppose $p\in P\setminus\bigcup_{i\in\gamma k}B^{0}_{i}$ , then $\mathsf{dist}(p,T)>R$ . Let $j\geq 1$ be such that $2^{j-1}R\leq\mathsf{dist}(p,T)\leq 2^{j}R$ . Hence, we have that $2^{j}R\leq 2\mathsf{dist}(p,T)$ . Therefore, using $\mathsf{dist}(p,X)-\frac{\varepsilon d(p,T)}{2\alpha}\leq\mathsf{dist}(p^{% \prime},X)\leq\mathsf{dist}(p,X)+\frac{\varepsilon d(p,T)}{2\alpha}$ , we have

\max\{\mathsf{dist}(p,X)-\nicefrac{{\varepsilon d(p,T)}}{{2\alpha}}-r,0\}\leq% \mathsf{dist}_{r}(p^{\prime},X)\leq\max\{\mathsf{dist}(p,X)+\nicefrac{{% \varepsilon d(p,T)}}{{2\alpha}}-r,0\}

This implies, $\mathsf{dist}_{r}(p,X)-\nicefrac{{\varepsilon d(p,T)}}{{2\alpha}}\leq\mathsf{% dist}_{r}(p^{\prime},X)\leq\mathsf{dist}_{r}(p,X)+\nicefrac{{\varepsilon d(p,T% )}}{{2\alpha}}$ . Thus, we have

\sum_{p\in P\setminus P_{0}}|\mathsf{dist}_{r}(p,X)-\mathsf{dist}_{r}(p^{% \prime},X)|\leq\sum_{p\in P\setminus P_{0}}\frac{\varepsilon}{2\alpha}\mathsf{% dist}(p,T)\leq\frac{{\sf OPT}_{r}}{2}\leq\frac{\varepsilon\mathsf{cost}_{r}(P,% X)}{2}.

Finally, we have $|{\sf wcost}_{r}(P^{\prime},X)-\mathsf{cost}_{r}(P,X)|\leq\varepsilon\mathsf{% cost}_{r}(P,X)$ , as desired.

To finish the proof, we invoke the coreset construction algorithm using the approximate set $T$ obtained from the following lemma. At a high level, to obtain this lemma, we start from an $(18,6)$ -bicriteria approximation for Hybrid $k$ -Clustering from [23, 13], and use the fact that, a ball of radius $O(r)$ can be decomposed into $2^{O(d)}$ balls of radius $r$ , converting the guarantee from $\mathsf{dist}_{6r}(\cdot,\cdot)$ to $\mathsf{dist}_{r}(\cdot,\cdot)$ .

Lemma 23 (Approximate solution $T$ for coreset construction).

There is a polynomial-time algorithm that, given an instance $\mathcal{I}=(P,\mathbb{F},\mathsf{dist},r)$ of Hybrid $k$ -Clustering in doubling metric of dimension $d$ , computes $T\subseteq P\cup\mathbb{F},|T|\leq 2^{O(d)}k$ such that $\mathsf{cost}_{r}(P,T)\leq 36\cdot{\sf OPT}_{r}$ , where ${\sf OPT}_{r}$ is the optimal cost for $\mathcal{I}$ .

$\hfill\blacktriangleleft$

Proof.

Let $A$ be $(18,6)$ -bicriteria solution for $\mathcal{I}$ obtained from [14], as mentioned in [23].That is $\mathsf{cost}_{6r}(P,A)\leq 18{\sf OPT}_{r}$ . Consider $B_{a}:={\sf ball}(a,12r)$ for $a\in A$ , and decompose $B_{a}$ into $2^{O(d)}$ smaller balls, each of radius $r/2$ – note that this follows from the fact that the metric space has doubling dimension $d$ . For each smaller ball $b$ such that $b\cap(P\cup\mathbb{F})\neq\emptyset$ , add an arbitrary $t\in b\cap(P\cup\mathbb{F})$ to $T$ . Finally, add $A$ to $T$ . Hence, $|T|=|A|+2^{O(d)}|A|=k2^{O(d)}$ .

It is easy to see that, for every $p\in\bigcup_{c\in A}{\sf ball}(c,12r)$ , there is some $q\in T$ , such that $\mathsf{dist}(p,q)\leq r$ . Now, consider some $p^{\prime}\not\in\bigcup_{c\in A}{\sf ball}(c,12r)$ . Note that $\mathsf{dist}_{6r}(p,A)\geq 6r$ , which implies that $\mathsf{dist}(p,A)\leq 2\cdot\mathsf{dist}_{6r}(p,A)$ . Therefore, $\mathsf{dist}_{r}(p,T)\leq\mathsf{dist}_{r}(p,A)\leq\mathsf{dist}(p,A)\leq 2% \mathsf{dist}_{6r}(p,A)$ . Therefore, it follows that for all $p\in P$ , $\mathsf{dist}_{r}(p,T)\leq 2\cdot\mathsf{dist}_{6r}(p,A)$ . Which implies that,

\mathsf{cost}_{r}(p,T)\leq 2\cdot\mathsf{cost}_{r}(p,A)\leq 36\cdot{\sf OPT}_{% r}.

This concludes the proof of the lemma. $\hfill\blacktriangleleft$

6 Conclusion

In this paper, we revisit Hybrid $k$ -Clustering, which was introduced and studied recently by Fomin et al. [23]. We resolve two open questions explicitly asked in their work, namely, for continuous Euclidean instances from ^d, (1) we obtain an FPT-AS for Hybrid $k$ -Clustering that does not have an FPT dependence on the dimension $d$ (and in fact, the dependence on $k$ is $2^{O(k\log k)}$ instead $2^{\operatorname{poly}(k)}$ as in [23]), and (2) we design coresets for the same. Indeed, our technique also generalizes to the $(k,z)$ -clustering variant of the problem, which was implicitly considered in [23], but was not completely resolved. To obtain our algorithmic result, we build upon insights from the recent framework of Abbasi et al. [1] for clustering in metric spaces of bounded algorithmic scatter dimension that encapsulates a broad class of metric spaces. Thus, our result shows that the potential of the framework introduced in [1] extends to clustering problems beyond that captured by the monotone norm setting, thus paving the way for obtaining FPT-ASes for other clustering problems using the similar technique. However, several interesting questions remain.

Firstly, the framework of [1] is inherently randomized due to key sampling steps, and its derandomization remains an intriguing open question. In particular, derandomizing the step that samples a witness in our algorithm is an interesting challenge. In another direction, now that the approximation landscape of the vanilla version of Hybrid $k$ -Clustering is beginning to be well-understood, it is natural to explore constrained variants of the problem such as those involving fairness or capacity constraints.

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. 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.
[2] 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. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 6:1–6:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ICALP.2024.6.
[3] Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, and Jie Xue. Clustering what matters: Optimal approximation for clustering with outliers. J. Artif. Intell. Res., 78:143–166, 2023. doi:10.1613/JAIR.1.14883.
[4] Barbara Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems. Mathematics of Operations Research, 35(1):pages 79–101, 2010.
[5] Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for euclidean k-medians and related problems. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, pages 106–113, New York, NY, USA, 1998. ACM. doi:10.1145/276698.276718.
[6] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544–562, 2004. doi:10.1137/S0097539702416402.
[7] 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.
[8] Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On coresets for fair clustering in metric and euclidean spaces and their applications. J. Comput. Syst. Sci., 142:103506, 2024. doi:10.1016/J.JCSS.2024.103506.
[9] Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann. New approximability results for the robust $k$ -median problem. In Scandinavian Workshop on Algorithm Theory (SWAT’14), pages 50–61. Springer, 2014. doi:10.1007/978-3-319-08404-6_5.
[10] Romain Bourneuf and Marcin Pilipczuk. Bounding $\varepsilon$ -scatter dimension via metric sparsity. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (to appear), 2025.
[11] Vladimir Braverman, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for ordered weighted clustering. In International Conference on Machine Learning (ICML’19), pages 744–753. PMLR, 2019. URL: http://proceedings.mlr.press/v97/braverman19a.html.
[12] 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.
[13] Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 67:1–67:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.ICALP.2016.67.
[14] 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. doi:10.4230/LIPICS.ICALP.2018.29.
[15] Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 126–137. ACM, 2019. doi:10.1145/3313276.3316322.
[16] Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, and Chris Schwiegelshohn. Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 940–986. SIAM, 2023. doi:10.1137/1.9781611977554.CH37.
[17] 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.
[18] Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1–41:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ICALP.2019.41.
[19] Vincent Cohen-Addad, Michał Pilipczuk, and Marcin Pilipczuk. A polynomial-time approximation scheme for facility location on planar graphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 560–581. IEEE, 2019.
[20] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Proceddings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 169–182. ACM, 2021. doi:10.1145/3406325.3451022.
[21] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[22] Tomás Feder and Daniel H. Greene. Optimal algorithms for approximate clustering. In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 434–444. ACM, 1988. doi:10.1145/62212.62255.
[23] Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Hybrid k-clustering: Blending k-median and k-center. In Amit Kumar and Noga Ron-Zewi, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK, volume 317 of LIPIcs, pages 4:1–4:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.APPROX/RANDOM.2024.4.
[24] 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.
[25] 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. doi:10.1145/3442188.3445906.
[26] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 291–300. ACM, 2004. doi:10.1145/1007352.1007400.
[27] Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, 32(1):130–136, 1985. doi:10.1145/2455.214106.
[28] Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180–184, 1985. URL: http://www.jstor.org/stable/3689371, doi:10.1287/MOOR.10.2.180.
[29] Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 731–740. ACM, 2002. doi:10.1145/509907.510012.
[30] Kamal Jain and Vijay 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. doi:10.1145/375827.375845.
[31] Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 646–659. ACM, 2018. doi:10.1145/3188745.3188882.
[32] Alfred A Kuehn and Michael J Hamburger. A heuristic program for locating warehouses. Management science, 9(4):643–666, 1963.
[33] 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.
[34] 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. doi:10.1145/1667053.1667054.
[35] Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput., 222:45–58, 2013. doi:10.1016/J.IC.2012.01.007.
[36] S. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28(2):129–137, March 1982. doi:10.1109/TIT.1982.1056489.
[37] Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan. The planar k-means problem is np-hard. Theor. Comput. Sci., 442:13–21, 2012. doi:10.1016/J.TCS.2010.05.034.
[38] Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Conference on Learning Theory (COLT’21), pages 3246–3264. PMLR, 2021. URL: http://proceedings.mlr.press/v134/makarychev21a.html.
[39] Dániel Marx. Parameterized complexity of independence and domination on geometric graphs. In Hans L. Bodlaender and Michael A. Langston, editors, Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, volume 4169 of Lecture Notes in Computer Science, pages 154–165. Springer, 2006. doi:10.1007/11847250_14.
[40] Nimrod Megiddo and Kenneth J Supowit. On the complexity of some common geometric location problems. SIAM journal on computing, 13(1):182–196, 1984. doi:10.1137/0213014.
[41] John F. Stollsteimer. A working model for plant numbers and locations. Journal of Farm Economics, 45(3):631–645, 1963. URL: http://www.jstor.org/stable/1235442.
[42] 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.
[43] Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, and Dan Feldman. New coresets for projective clustering and applications. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 5391–5415. PMLR, 2022. URL: https://proceedings.mlr.press/v151/tukan22a.html.

[bib.bib1] [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. 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.

[bib.bib2] [2] 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. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 6:1–6:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ICALP.2024.6.

[bib.bib3] [3] Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, and Jie Xue. Clustering what matters: Optimal approximation for clustering with outliers. J. Artif. Intell. Res., 78:143–166, 2023. doi:10.1613/JAIR.1.14883.

[bib.bib4] [4] Barbara Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems. Mathematics of Operations Research, 35(1):pages 79–101, 2010.

[bib.bib5] [5] Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for euclidean k-medians and related problems. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, pages 106–113, New York, NY, USA, 1998. ACM. doi:10.1145/276698.276718.

[bib.bib6] [6] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544–562, 2004. doi:10.1137/S0097539702416402.

[bib.bib7] [7] 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.

[bib.bib8] [8] Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On coresets for fair clustering in metric and euclidean spaces and their applications. J. Comput. Syst. Sci., 142:103506, 2024. doi:10.1016/J.JCSS.2024.103506.

[bib.bib9] [9] Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann. New approximability results for the robust $k$ -median problem. In Scandinavian Workshop on Algorithm Theory (SWAT’14), pages 50–61. Springer, 2014. doi:10.1007/978-3-319-08404-6_5.

[bib.bib10] [10] Romain Bourneuf and Marcin Pilipczuk. Bounding $\varepsilon$ -scatter dimension via metric sparsity. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (to appear), 2025.

[bib.bib11] [11] Vladimir Braverman, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for ordered weighted clustering. In International Conference on Machine Learning (ICML’19), pages 744–753. PMLR, 2019. URL: http://proceedings.mlr.press/v97/braverman19a.html.

[bib.bib12] [12] 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.

[bib.bib13] [13] Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 67:1–67:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.ICALP.2016.67.

[bib.bib14] [14] 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. doi:10.4230/LIPICS.ICALP.2018.29.

[bib.bib15] [15] Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 126–137. ACM, 2019. doi:10.1145/3313276.3316322.

[bib.bib16] [16] Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, and Chris Schwiegelshohn. Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 940–986. SIAM, 2023. doi:10.1137/1.9781611977554.CH37.

[bib.bib17] [17] 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.

[bib.bib18] [18] Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1–41:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ICALP.2019.41.

[bib.bib19] [19] Vincent Cohen-Addad, Michał Pilipczuk, and Marcin Pilipczuk. A polynomial-time approximation scheme for facility location on planar graphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 560–581. IEEE, 2019.

[bib.bib20] [20] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Proceddings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 169–182. ACM, 2021. doi:10.1145/3406325.3451022.

[bib.bib21] [21] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib22] [22] Tomás Feder and Daniel H. Greene. Optimal algorithms for approximate clustering. In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 434–444. ACM, 1988. doi:10.1145/62212.62255.

[bib.bib23] [23] Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Hybrid k-clustering: Blending k-median and k-center. In Amit Kumar and Noga Ron-Zewi, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK, volume 317 of LIPIcs, pages 4:1–4:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.APPROX/RANDOM.2024.4.

[bib.bib24] [24] 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.

[bib.bib25] [25] 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. doi:10.1145/3442188.3445906.

[bib.bib26] [26] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 291–300. ACM, 2004. doi:10.1145/1007352.1007400.

[bib.bib27] [27] Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, 32(1):130–136, 1985. doi:10.1145/2455.214106.

[bib.bib28] [28] Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180–184, 1985. URL: http://www.jstor.org/stable/3689371, doi:10.1287/MOOR.10.2.180.

[bib.bib29] [29] Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 731–740. ACM, 2002. doi:10.1145/509907.510012.

[bib.bib30] [30] Kamal Jain and Vijay 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. doi:10.1145/375827.375845.

[bib.bib31] [31] Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 646–659. ACM, 2018. doi:10.1145/3188745.3188882.

[bib.bib32] [32] Alfred A Kuehn and Michael J Hamburger. A heuristic program for locating warehouses. Management science, 9(4):643–666, 1963.

[bib.bib33] [33] 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.

[bib.bib34] [34] 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. doi:10.1145/1667053.1667054.

[bib.bib35] [35] Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput., 222:45–58, 2013. doi:10.1016/J.IC.2012.01.007.

[bib.bib36] [36] S. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28(2):129–137, March 1982. doi:10.1109/TIT.1982.1056489.

[bib.bib37] [37] Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan. The planar k-means problem is np-hard. Theor. Comput. Sci., 442:13–21, 2012. doi:10.1016/J.TCS.2010.05.034.

[bib.bib38] [38] Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Conference on Learning Theory (COLT’21), pages 3246–3264. PMLR, 2021. URL: http://proceedings.mlr.press/v134/makarychev21a.html.

[bib.bib39] [39] Dániel Marx. Parameterized complexity of independence and domination on geometric graphs. In Hans L. Bodlaender and Michael A. Langston, editors, Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, volume 4169 of Lecture Notes in Computer Science, pages 154–165. Springer, 2006. doi:10.1007/11847250_14.

[bib.bib40] [40] Nimrod Megiddo and Kenneth J Supowit. On the complexity of some common geometric location problems. SIAM journal on computing, 13(1):182–196, 1984. doi:10.1137/0213014.

[bib.bib41] [41] John F. Stollsteimer. A working model for plant numbers and locations. Journal of Farm Economics, 45(3):631–645, 1963. URL: http://www.jstor.org/stable/1235442.

[bib.bib42] [42] 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.

[bib.bib43] [43] Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, and Dan Feldman. New coresets for projective clustering and applications. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 5391–5415. PMLR, 2022. URL: https://proceedings.mlr.press/v151/tukan22a.html.

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1 (Bicriteria FPT-AS for Euclidean Spaces).

Theorem 2 (Informal version of Theorem 9).

Theorem 3 (Coreset for Hybrid k-Clustering).

1.1 Technical Overview

Scatter Dimension.

Working with the inflated radius.

Bounding the aspect ratio of the radii.

2 Background on Algorithmic Scatter Dimension

Definition 4 (Ball Intersection Problem).

Definition 5 (Algorithmic ε-Scatter Dimension).

Lemma 6 (♠).

3 Bicriteria FPT Approximation Scheme

3.1 Algorithm

3.2 Analysis

Lemma 7.

Lemma 8.

Theorem 9 (Main Theorem).

3.2.1 Bounding runtime using Algorithmic Scatter Dimension

Lemma 10 (Feasible upper bounds).

Proof.

Lemma 11 (Lemma V.5 of [1]).

Bounding aspect ratio of radii

Lemma 12.

Proof.

Claim 13.

Proof.

Proof of Lemma 7.

3.2.2 Bounding success probability

Definition 14 (Consistency).

Definition 15 (Contribution and Witness).

Claim 16 (♠).

Definition 17 (Different subsets of witnesses).

Case 1: 𝑪𝑾𝗻𝗲𝗮𝗿≥𝜺𝟏𝟎𝟎⁢𝑪𝑷.

Lemma 18 (Nearby witness lemma).

Proof.

Case 2: 𝑪𝑾𝗻𝗲𝗮𝗿<𝜺𝟏𝟎𝟎⁢𝑪𝑷.

Lemma 19 (Faraway witness lemma).

Proof.

Observation 20 (♠).

Claim 21.

Proof.

Lemma 22.

Proof.

Proof of Lemma 8.

4 Extensions of the Bicriteria FPT-AS

5 Coreset

Proof.

Lemma 23 (Approximate solution T for coreset construction).

Proof.

6 Conclusion

References

Theorem 3 (Coreset for Hybrid $k$ -Clustering).

Definition 5 (Algorithmic $\varepsilon$ -Scatter Dimension).

Lemma 6 ( $\spadesuit$ ).

Claim 16 ( $\spadesuit$ ).

Case 1: $C_{W_{\sf near}}\geq\frac{\varepsilon}{100}C_{P}$ .

Case 2: $C_{W_{\sf near}}<\frac{\varepsilon}{100}C_{P}$ .

Observation 20 ( $\spadesuit$ ).

Lemma 23 (Approximate solution $T$ for coreset construction).