$k$-center Clustering under Perturbation Resilience

Introduction

Clustering is a fundamental problem in combinatorial optimization with a wide range of applications including bioinformatics, computer vision, text analysis, and countless others. The underlying goal is to partition a given set of points to maximize similarity within a partition and minimize similarity across different partitions. A common approach to clustering is to consider an objective function over all possible partitionings and seek solutions that are optimal according to the objective. Given a set of points (and a distance metric), common clustering objectives include finding $k$ centers to minimize the sum of the distance from each point to its closest center ($k$-median), or to minimize the maximum distance from a point to its closest center ($k$-center).

Traditionally, the theory of clustering (and more generally, the theory of algorithms) has focused on the analysis of worst-case instances (Arya et al., 2004; Byrka et al., 2015; Charikar et al., 1999, 2001; Chen, 2008; Gonzalez, 1985; Makarychev et al., 2016). For example, it is well known the popular objective functions are provably NP-hard to optimize exactly or even approximately (APX-hard) (Gonzalez, 1985; Jain et al., 2002; Lee et al., 2017), so research has focused on finding approximation algorithms. While this perspective has led to many elegant approximation algorithms and lower bounds for worst-case instances, it is often overly pessimistic of an algorithm’s performance on “typical” instances or real world instances. A rapidly developing line of work in the algorithms community, the so-called beyond worst-case analysis of algorithms (BWCA), considers the design and analysis of problem instances under natural structural properties which may be satisfied in real-world applications. For example, the popular notion of $\alpha$-perturbation resilience, introduced by Bilu and Linial (2012), considers instances such that the optimal solution does not change when the input distances are allowed to increase by up to a factor of $\alpha$. The goals of BWCA are twofold: (1) to design new algorithms with strong performance guarantees under the added assumptions (Balcan et al., 2013; Hardt and Roth, 2013; Kumar et al., 2004; Roughgarden, 2014), and (2) to prove strong guarantees under BWCA assumptions for existing algorithms used in practice (Makarychev et al., 2014; Ostrovsky et al., 2012; Spielman and Teng, 2004). An example of goal (1) is a series of work focused on finding exact algorithms for $k$-median, $k$-means, and $k$-center clustering under $\alpha$-perturbation resilience (Awasthi et al., 2012; Balcan and Liang, 2016; Angelidakis et al., 2017). The goal in this line of work is to find the minimum value of $\alpha\geq 1$ for which optimal clusterings of $\alpha$-perturbation resilient instances can be found efficiently. Two examples of goal (2) are as follows. Ostrovsky et al. showed that $k$-means++ outputs a near-optimal clustering, as long as the data satisfies a natural clusterability criterion (Ostrovsky et al., 2012), and Spielman and Teng (2004) established the expected runtime of the simplex method is $O(n)$ under smoothed analysis.

In approaches for answering goals (1) and (2), researchers have developed an array of sophisticated tools exploiting the structural properties of such instances leading to algorithms which can output the optimal solution. However, overly exploiting a BWCA assumption can lead to algorithms that perform poorly when the input data does not exactly satisfy the given assumption. Indeed, recent analyses and technical tools are susceptible to small deviations from the BWCA assumptions which can propagate when just a small fraction of the data does not satisfy the assumption. For example, some recent algorithms make use of a dynamic programming subroutine which crucially need the entire instance to satisfy the specific structure guaranteed by the BWCA assumption. To continue the efforts of BWCA in bridging the theory-practice gap, it is essential to study algorithms whose guarantees degrade gracefully to address scenarios that present mild deviations from the standard BWCA assumptions. Another downside of existing approaches is that BWCA assumptions are often not efficiently verifiable. This creates a catch-22 scenario: it is only useful to run the algorithms if the data satisfies certain assumptions, but a user cannot check these assumptions efficiently. For example, by nature of $\alpha$-perturbation resilience (that the optimal clustering does not change under all $\alpha$-perturbations of the input), it is not known how to test this condition without computing the optimal clustering over $\Omega\left(2^{n}\right)$ different perturbations. To alleviate these issues, in this work we also focus on what we propose should be a third goal for BWCA: to show (new or existing) algorithms whose performance degrades gracefully on instances that only partially meet the BWCA assumptions.

In this work, we address goals (1), (2), and (3) of BWCA by providing robust algorithms which give the optimal solution under perturbation resilience, and also perform well when the data is partially perturbation resilient, or not at all perturbation resilient. These algorithms act as an interpolation between worst-case and beyond worst-case analysis. We focus on the symmetric/asymmetric $k$-center objective under perturbation resilience. Our algorithms simultaneously output the optimal clusters from the stable regions of the data, while achieving state-of-the-art approximation ratios over the rest of the data. In most cases, our algorithms are natural modifications to existing approximation algorithms, thus achieving goal (2) of BWCA. To achieve these two-part guarantees, we define the notion of perturbation resilience on a subset of the datapoints. All prior work has only studied perturbation resilience as it applies to the entire dataset. Informally, a subset $S^{\prime}\subseteq S$ satisfies $\alpha$-perturbation resilience if all points $v\in S^{\prime}$ remain in the same optimal cluster under any $\alpha$-perturbation to the input. We show that our algorithms return all optimal clusters from these locally stable regions. Most of our results also apply under the recently defined, weaker condition of $\alpha$-metric perturbation resilience (Angelidakis et al., 2017), which states that the optimal solution cannot change under the metric closure of any $\alpha$-perturbation. We list all our results in Table 1, and give a summary of the results and techniques below.

In Section 3, we show that any 2-approximation algorithm for $k$-center will always return the clusters satisfying $2$-perturbation resilience. Therefore, since there are well-known 2-approximation algorithms for symmetric $k$-center, our analysis shows these will output the optimal clustering under 2-perturbation resilience. For asymmetric $k$-center, we give a new algorithm which outputs the optimal clustering under 2-perturbation resilience. It works by first computing the “symmetrized set”, or the points which demonstrate a rough symmetry. We show how to optimally cluster the symmetrized set, and then we show how to add back the highly asymmetric points into their correct clusters.

In Section 3.2.2, we prove there is no polynomial time algorithm for symmetric $k$-center under $(2-\delta)$-perturbation resilience unless $NP=RP$, which shows that our perturbation resilience results are tight for both symmetric and asymmetric $k$-center. In particular, it implies that we have identified the exact moment ($\alpha=2$) where the problem switches from efficiently computable to NP-hard, for both symmetric and asymmetric $k$-center. For this hardness result, we use a reduction from a variant of perfect dominating set. To show that this variant is itself hard, we construct a chain of parsimonious reductions (reductions which conserve the number of solutions) from 3-dimensional matching to perfect dominating set.

Our upper bound for asymmetric $k$-center under 2-PR and lower bound for symmetric $k$-center under $(2-\delta)$-PR illustrate a surprising relationship between symmetric and asymmetric $k$-center instances under perturbation resilience. Unlike approximation ratio, for which symmetric $k$-center is easily solved to a factor of 2 but asymmetric $k$-center cannot be approximated to any constant factor, both symmetric and asymmetric $k$-center can be solved optimally under resilience to 2-perturbations. Overall, this is the first tight result quantifying the power of perturbation resilience for a canonical combinatorial optimization problem.

In Section 5, we apply our results from Section 3 to the local perturbation resilience setting. For symmetric $k$-center, we show that any 2-approximation outputs all optimal clusters from 2-perturbation resilient regions. For asymmetric $k$-center, we design a new algorithm based off of the worst-case $O(\log^{*}n)$ approximation algorithm due to Vishwanathan (1996), which is tight (Chuzhoy et al., 2005). We give new insights into this algorithm, which allow us to show a modification of the algorithm which outputs all optimal clusters from 2-perturbation resilient regions, while keeping the worst-case $O(\log^{*}n)$ guarantee overall. If the entire dataset satisfies 2-perturbation resilience, then our algorithm outputs the optimal clustering. We combine the tools of Vishwanathan with the perturbation resilience assumption to prove this two-part guarantee. Specifically, we use the notion of a center-capturing vertex (CCV), which is used in the first phase of the approximation algorithm to pull out supersets of clusters. We show that each optimal center from a 2-perturbation resilient subset is a CCV and satisfies a separation property; we prove this by carefully constructing a 2-perturbation in which points from other clusters cannot be too close to the center without causing a contradiction. The structure allows us to modify the approximation algorithm of Vishwanathan (1996) to ensure that optimal clusters from perturbation resilient subsets are pulled out separately in the first phase. All of our guarantees hold under the weaker notion of metric perturbation resilience.

In Section 6, we consider $(\alpha,\epsilon)$-perturbation resilience, which states that at most $\epsilon n$ total points can swap into or out of each cluster under any $\alpha$-perturbation. For symmetric $k$-center, we show that any 2-approximation algorithm will return the optimal clusters from $(3,\epsilon)$-perturbation resilient regions, assuming a mild lower bound on optimal cluster sizes, and for asymmetric $k$-center, we give an algorithm which outputs a clustering that is $\epsilon$-close to the optimal clustering. Our main structural tool is showing that if any single point $v$ is close to an optimal cluster other than its own, then $k-1$ centers achieve the optimal radius under a carefully constructed 3-perturbation. Any other point we add to the set of centers must create a clustering that is $\epsilon$-close to the optimal clustering, and we show all of these sets cannot simultaneously be consistent with one another, thus causing a contradiction. A key concept in our analysis is defining the notion of a cluster-capturing center, which allows us to reason about which points can capture a cluster when its center is removed.

2 Related work

There are three classic 2-approximations for $k$-center from the 1980’s (Gonzalez, 1985; Hochbaum and Shmoys, 1985; Dyer and Frieze, 1985), which are known to be tight (Hochbaum and Shmoys, 1985). Asymmetric $k$-center proved to be a much harder problem. The first nontrivial result was an $O(\log^{*}n)$ approximation algorithm (Vishwanathan, 1996), and this was later improved to $O(\log^{*}k)$ (Archer, 2001). This result was later proven to be asymptotically tight (Chuzhoy et al., 2005).

The first constant-factor approximation algorithm for $k$-median was given by Charikar et al. (1999), and the current best approximation ratio is 2.675 by Byrka et al. (2015). Jain et al. (2002) proved $k$-median is NP-hard to approximate to a factor better than 1.73.

Perturbation resilience was introduced by Bilu and Linial (2012), who showed algorithms that outputted the optimal solution for max cut under $\Omega(\sqrt{n})$-perturbation resilience (this was later improved by Makarychev et al. (2014)). The study of clustering under perturbation resilience was initiated by Awasthi et al. (2012), who provided an optimal algorithm for center-based clustering objectives (which includes $k$-median, $k$-means, and $k$-center clustering, as well as other objectives) under 3-perturbation resilience. This result was improved by Balcan and Liang (2016), who showed an algorithm for center-based clustering under $(1+\sqrt{2})$-perturbation resilience. They also gave a near-optimal algorithm for $k$-median under $(2+\sqrt{3},\epsilon)$-perturbation resilience when the optimal clusters are not too small.

Recently, Angelidakis et al. (2017) gave algorithms for center-based clustering (including $k$-median, $k$-means, and $k$-center) under 2-perturbation resilience, and defined the more general notion of metric perturbation resilience, although their algorithm does not extend to the $(\alpha,\epsilon)$-perturbation resilience or local perturbation resilience settings. Cohen-Addad and Schwiegelshohn (2017) showed that local search outputs the optimal $k$-median, $k$-means, and $k$-center solution when the data satisfies a stronger variant of 3-perturbation resilience, in which both the optimal clustering and optimal centers are not allowed to change under any 3-perturbation. Perturbation resilience has also been applied to other problems, such as min multiway cut, the traveling salesman problem, finding Nash equilibria, metric labeling, and facility location (Makarychev et al., 2014; Mihalák et al., 2011; Balcan and Braverman, 2017; Lang et al., 2017; Manthey and Tijink, 2018).

Vijayaraghavan et al. (2017) study $k$-means under additive perturbation resilience, in which the optimal solution cannot change under additive perturbations to the input distances. Deshpande et al. (2018) gave an algorithm for Euclidean $k$-means under perturbation resilience which runs in time linear in $n$ and the dimension $d$, and exponentially in $k$ and $\frac{1}{\alpha-1}$. Chekuri and Gupta (2018) showed the natural LP relaxation of $k$-center and asymmetric $k$-center is integral for 2-perturbation resilient instances. They also define a new model of perturbation resilience for clustering with outliers, and they show the algorithm of Angelidakis et al. (2017) exactly solves clustering with outliers under 2-perturbation resilience, and they further show the natural LP relaxation for $k$-center with outliers is integral for 2-perturbation resilient instances. Their algorithms have the desirable property that either they output the optimal solution, or they guarantee the input did not satisfy 2-perturbation resilience (but note this is not the same thing as determining whether or not a given instance satisfies perturbation resilience).

A related notion, approximation stability (Balcan et al., 2013), states that any $(1+\alpha)$-approximation to the objective must be $\epsilon$-close to the target clustering. There are several positive results for $k$-means, $k$-median (Balcan et al., 2013, 2009; Gupta et al., 2014), and min-sum (Balcan et al., 2013; Balcan and Braverman, 2009; Voevodski et al., 2011) under approximation stability. Ostrovsky et al. (2012) show how to efficiently cluster instances in which the $k$-means clustering cost is much lower than the $(k-1)$-means cost. Kumar and Kannan (2010) give an efficient clustering algorithm for instances in which the projection of any point onto the line between its cluster center to any other cluster center is a large additive factor closer to its own center than the other center. This result was later improved along multiple axes by Awasthi and Sheffet (2012). There are many other works that show positive results for different natural notions of stability in various settings (Arora et al., 2012; Awasthi et al., 2010; Gupta et al., 2014; Hardt and Roth, 2013; Kumar and Kannan, 2010; Kumar et al., 2004; Roughgarden, 2014).

Preliminaries and basic properties

Some of our results assume distance functions which are metrics, and some of our results assume asymmetric distance functions. A distance function $d$ is a metric if

for all $u,v$, $d(u,v)=0$ if and only if $u=v$,

for all $u,v,w$, $d(u,w)\leq d(u,v)+d(v,w)$, and

An asymmetric distance function satisifies (1), (2), and (3), but not (4).

Now we formally define perturbation resilience, a notion introduced by Bilu and Linial (2012). $d^{\prime}$ is called an $\alpha$-perturbation of the distance function $d$, if for all $u,v\in S$, $d(u,v)\leq d^{\prime}(u,v)\leq\alpha d(u,v)$. We only consider perturbations in which the distances increase because without loss of generality we can scale the distances to simulate decreasing distances.

(Perturbation resilience) A clustering instance $(S,d)$ satisfies $\alpha$-perturbation resilience ($\alpha$-PR) if for any $\alpha$-perturbation $d^{\prime}$ of $d$, the optimal clustering $\mathcal{C^{\prime}}$ under $d^{\prime}$ is unique and equal to $\mathcal{OPT}$.

Note that the optimal centers might change under an $\alpha$-perturbation, but the optimal clustering must stay the same. We also consider a relaxed variant of $\alpha$-perturbation resilience, called $(\alpha,\epsilon)$-perturbation resilience, that allows a small change in the optimal clustering when distances are perturbed. We say that two clusterings $\mathcal{C}$ and $\mathcal{C}^{\prime}$ are $\epsilon$-close if $\min_{\sigma}\sum_{i=1}^{k}\left|C_{i}\setminus C_{\sigma(i)}^{\prime}\right|\leq\epsilon n$, where $\sigma$ is a permutation on $[k]$.

($(\alpha,\epsilon)$-perturbation resilience) A clustering instance $(S,d)$ satisfies $(\alpha,\epsilon)$-perturbation resilience if for any $\alpha$-perturbation $d^{\prime}$ of $d$, any optimal clustering $\mathcal{C}^{\prime}$ under $d^{\prime}$ is $\epsilon$-close to $\mathcal{OPT}$.

In Definitions 2.1 and 2.2, we do not assume that the $\alpha$-perturbations satisfy the triangle inequality. Angelidakis et al. (2017) recently studied the weaker definition in which the $\alpha$-perturbations must satisfy the triangle inequality, called metric perturbation resilience. We can update these definitions accordingly. For symmetric clustering objectives, $\alpha$-metric perturbations are restricted to metrics. For asymmetric clustering objectives, the $\alpha$-metric perturbations must satisfy the directed triangle inequality.

(Metric perturbation resilience) A clustering instance $(S,d)$ satisfies $\alpha$-metric perturbation resilience ($\alpha$-MPR) if for any $\alpha$-metric perturbation $d^{\prime}$ of $d$, the optimal clustering $\mathcal{C^{\prime}}$ under $d^{\prime}$ is unique and equal to $\mathcal{OPT}$.

In our arguments, we will sometimes convert a non-metric perturbation $d^{\prime}$ into a metric perturbation by taking the metric completion $d^{\prime\prime}$ of $d^{\prime}$ (also referred to as the shortest-path metric on $d^{\prime}$) by setting the distances in $d^{\prime\prime}$ as the length of the shortest path on the graph whose edges are the lengths in $d^{\prime}$. Note that for all $u,v$, we have $d(u,v)\leq d^{\prime\prime}(u,v)$ since $d$ was originally a metric.

Now we define perturbation resilience for an optimal cluster rather than the entire dataset. All prior work has considered perturbation resilience with respect to the entire dataset.

(Local perturbation resilience) Given a clustering instance $(S,d)$ with optimal clustering $\mathcal{C}=\{C_{1},\dots,C_{k}\}$, an optimal cluster $C_{i}$ satisfies $\alpha$-perturbation resilience ($\alpha$-PR) if for any $\alpha$-perturbation $d^{\prime}$ of $d$, the optimal clustering $\mathcal{C}^{\prime}$ under $d^{\prime}$ is unique and contains $C_{i}$.

As a sanity check, we show that a clustering is perturbation resilient if and only if every optimal cluster satisfies perturbation resilience.

A clustering instance $(S,d)$ satisfies $\alpha$-PR if and only if each optimal cluster satisfies $\alpha$-PR.

Given a clustering instance $(S,d)$, the forward direction follows by definition: assume $(S,d)$ satisfies $\alpha$-PR, and given an optimal cluster $C_{i}$, then for each $\alpha$-perturbation $d^{\prime}$, the optimal clustering stays the same under $d^{\prime}$, therefore $C_{i}$ is contained in the optimal clustering under $d^{\prime}$. Now we prove the reverse direction. Given a clustering instance with optimal clustering $\mathcal{C}$, and given an $\alpha$-perturbation $d^{\prime}$, let the optimal clustering under $d^{\prime}$ be $\mathcal{C}^{\prime}$. For each $C_{i}\in\mathcal{C}$, by assumption, $C_{i}$ satisfies $\alpha$-PR, so $C_{i}\in\mathcal{C}^{\prime}$. Therefore $\mathcal{C}=\mathcal{C}^{\prime}$. ∎

Next we define the local version of $(\alpha,\epsilon)$-PR.

(Local $(\alpha,\epsilon)$-perturbation resilience) Given a clustering instance $(S,d)$ with optimal clustering $\mathcal{C}=\{C_{1},\dots,C_{k}\}$, an optimal cluster $C_{i}$ satisfies $(\alpha,\epsilon)$-PR if for any $\alpha$-perturbation $d^{\prime}$ of $d$, the optimal clustering $\mathcal{C}^{\prime}$ under $d^{\prime}$ contains a cluster $C_{i}^{\prime}$ which is $\epsilon$-close to $C_{i}$.

In Sections 5 and 6, we will consider a slightly stronger notion of local perturbation resilience. Informally, an optimal cluster satisfies $\alpha$-strong local perturbation resilience if it is $\alpha$-PR, and all nearby optimal clusters are also $\alpha$-PR. We will sometimes be able to prove guarantees for clusters satisfying strong local perturbation resilience which are not true under standard local perturbation resilience.

(Strong local perturbation resilience) Given a clustering instance $(S,d)$ with optimal clustering $\mathcal{C}=\{C_{1},\dots,C_{k}\}$, an optimal cluster $C_{i}$ satisfies $\alpha$-strong local perturbation resilience ($\alpha$-SLPR) if for each $j$ such that there exists $u\in C_{i}$, $v\in C_{j}$, and $d(u,v)\leq r^{*}$, then $C_{j}$ is $\alpha$-PR (any cluster that is close to $C_{i}$ must be $\alpha$-PR).

To conclude this section, we state a lemma for asymmetric (and symmetric) $k$-center which allows us to reason about a specific class of $\alpha$-perturbations which will be important throughout the paper. We give two versions of the lemma, each of which will be useful in different sections of the paper.

Given a clustering instance $(S,d)$ and $\alpha\geq 1$,

assume we have an $\alpha$-perturbation $d^{\prime}$ of $d$ with the following property: for all $p,q$, if $d(p,q)\geq r^{*}$ then $d^{\prime}(p,q)\geq\alpha r^{*}$. Then the optimal cost under $d^{\prime}$ is $\alpha r^{*}$.

assume we have an $\alpha$-perturbation $d^{\prime}$ of $d$ with the following property: for all $u,v$, either $d^{\prime}(u,v)=\min(\alpha r^{*},\alpha d(u,v))$ or $d^{\prime}(u,v)=\alpha d(u,v)$. Then the optimal cost under $d^{\prime}$ is $\alpha r^{*}$.

Assume there exists a set of centers $C^{\prime}=\{c_{1}^{\prime},\dots,c_{k}^{\prime}\}$ whose $k$-center cost under $d^{\prime}$ is $<\alpha r^{*}$. Then for all $i$ and $s\in\text{Vor}_{C^{\prime},d^{\prime}}(c_{i}^{\prime})$, $d^{\prime}(c_{i}^{\prime},s)<\alpha r^{*}$, implying $d(c_{i}^{\prime},s)<r^{*}$ by construction. It follows that the $k$-center cost of $C^{\prime}$ under $d$ is $r^{*}$, which is a contradiction. Therefore, the optimal cost under $d^{\prime}$ must be $\alpha r^{*}$.

Given $u,v$ such that $d(u,v)\geq r^{*}$, then $d^{\prime}(u,v)\geq\alpha r^{*}$ by construction. Now the proof follows from part one.

k𝑘k-center under perturbation resilience

In this section, we provide efficient algorithms for finding the optimal clustering for symmetric and asymmetric instances of $k$-center under $2$-perturbation resilience. Our results directly improve on the result by Balcan and Liang (2016) for symmetric $k$-center under $(1+\sqrt{2})$-perturbation resilience. We also show that it is NP-hard to recover $\mathcal{OPT}$ even for symmetric $k$-center instance under $(2-\delta)$-perturbation resilience. As an immediate consequence, our results are tight for both symmetric and asymmetric $k$-center instances. This is the first problem for which the exact value of perturbation resilience is found ($\alpha=2$), where the problem switches from efficiently computable to NP-hard.

First, we show that any $\alpha$-approximation algorithm returns the optimal solution for $\alpha$-perturbation resilient instances. An immediate consequence is an algorithm for symmetric $k$-center under 2-perturbation resilience. Next, we provide a novel algorithm for asymmetric $k$-center under 2-perturbation resilience. Finally, we show hardness of $k$-center under $(2-\delta)$-PR.

The following theorem shows that any $\alpha$-approximation algorithm for $k$-center will return the optimal solution on clustering instances that are $\alpha$-perturbation resilient.

Given a clustering instance $(S,d)$ satisfying $\alpha$-perturbation resilience for asymmetric $k$-center, and a set $C$ of $k$ centers which is an $\alpha$-approximation, i.e., $\forall p\in S$, $\exists c\in C$ such that $d(c,p)\leq\alpha r^{*}$, then the Voronoi partition induced by $C$ is the optimal clustering.

For a point $p\in S$, let $c(p):=\text{argmin}_{c\in C}d(c,p)$, the closest center in $C$ to $p$. The idea is to construct an $\alpha$-perturbation in which $C$ is the optimal solution by increasing all distances except between $p$ and $c(p)$, for all $p$. Then the theorem will follow by using the definition of perturbation resilience.

By assumption, $\forall p\in S$, $d(c(p),p)\leq\alpha r^{*}$. Create a perturbation $d^{\prime}$ as follows. Increase all distances by a factor of $\alpha$, except for all $p\in S$, set $d^{\prime}(c(p),p)=\min(\alpha d(c(p),p),\alpha r^{*})$ (recall in Definition 2.1, the perturbation need not satisfy the triangle inequality). Then no distances were increased by more than a factor of $\alpha$. And since we had that $d(c(p),p)\leq\alpha r^{*}$, no distances decrease either. Therefore, $d^{\prime}$ is an $\alpha$-perturbation of $d$. By Lemma 2.8, the optimal cost for $d^{\prime}$ is $\alpha r^{*}$. Also, $C$ achieves cost $\leq\alpha r^{*}$ by construction, so $C$ is an optimal set of centers under $d^{\prime}$. Then by $\alpha$-perturbation resilience, the Voronoi partition induced by $C$ under $d^{\prime}$ is the optimal clustering.

Finally, we show the Voronoi partition of $C$ under $d$ is the same as the Voronoi partition of $C$ under $d^{\prime}$. Given $p\in S$ whose closest point in $C$ is $c(p)$ under $d$, then under $d^{\prime}$, all distances from $p$ to $C\setminus\{c(p)\}$ increased by exactly $\alpha$, and $d(p,c(p))$ increased by $\leq\alpha$. Therefore, the closest point in $C$ to $p$ under $d^{\prime}$ is still $c(p)$. ∎

2 k𝑘k-center under 2-PR

An immediate consequence of Theorem 3.1 is that we have an exact algorithm for symmetric $k$-center under 2-perturbation resilience by running a simple 2-approximation algorithm (e.g., (Gonzalez, 1985; Hochbaum and Shmoys, 1985; Dyer and Frieze, 1985)). However, Theorem 3.1 only gives an algorithm for asymmetric $k$-center under $O(\log^{*}(k))$-perturbation resilience. Next, we show it is possible to substantially improve the latter result.

One of the challenges involved in dealing with asymmetric $k$-center instances is the fact that even though for all $p\in C_{i}$, $d(c_{i},p)\leq r^{*}$, the reverse distance, $d(p,c_{i})$, might be arbitrarily large. Such points for which $d(p,c_{i})\gg r^{*}$ pose a challenge to the structure of the clusters, as they can be very close to points or even centers of other clusters. To deal with this challenge, we first define a set of “good” points, $A$, such that $A=\{p\mid\forall q,d(q,p)\leq r^{*}\implies d(p,q)\leq r^{*}\}$. A “good” point is referred to as a center-capturing vertex in other works, e.g., (Vishwanathan, 1996). We formally define this notion in Section 5. Intuitively speaking, these points behave similarly to a set of points with symmetric distances up to a distance $r^{*}$. To explore this, we define a desirable property of $A$ with respect to the optimal clustering.

$A$ is said to respect the structure of $\mathcal{OPT}$ if

(2) for all $p\in S\setminus A$, if $A(p):=\arg\min_{q\in A}d(q,p)\in C_{i}$, then $p\in C_{i}$.

For all $i$, define $C_{i}^{\prime}=C_{i}\cap A$ (which is in fact the optimal clustering of $A$). Satisfying Definition 3.2 implies that if we can optimally cluster $A$, then we can optimally cluster the entire instance (formalized in Theorem 3.5). Thus our goal is to show that $A$ does indeed respect the structure of $\mathcal{OPT}$, and to show how to return $C_{1}^{\prime},\dots,C_{k}^{\prime}$.

Intuitively, $A$ is similar to a symmetric 2-perturbation resilient clustering instance. However, some structure is no longer there, for instance, a point $p$ may be at distance $\leq 2r^{*}$ from every point in a different cluster, which is not true for 2-perturbation resilient instances. This implies we cannot simply run a 2-approximation algorithm on the set $A$, as we did in the previous section. However, we show that the remaining structural properties are sufficient to optimally cluster $A$. To this end, we define two properties and show how they lead to an algorithm that returns $C_{1}^{\prime},\dots,C_{k}^{\prime}$, and help us prove that $A$ respects the structure of $\mathcal{OPT}$.

The first of these properties requires each point to be closer to its center than any point in another cluster.

Property (1): For all $p\in C_{i}^{\prime}$ and $q\in C_{j\neq i}^{\prime}$, $d(c_{i},p)<d(q,p)$.

The second property requires that any point within distance $r^{*}$ of a cluster center belongs to that cluster.

Property (2): For all $i\neq j$ and $q\in C_{j}$, $d(q,c_{i})>r^{*}$ (see Figure 1). Property (1) first appeared in the work of Awasthi et al. (2012), for symmetric clustering instances. A weaker variation of Property (2) was introduced by Balcan and Liang (2016), which showed that in $1+\sqrt{2}$-perturbation resilient instances for any cluster $C_{i}$ with radius $r_{i}$, $B_{r_{i}}(c_{i})=C_{i}$. Our Property (2) shows that this is true for a universal radius, $r^{*}$, even for $2$-perturbation resilient instances, and even for asymmetric instances.

Let us illustrate how these properties allow us to optimally cluster $A$. Other algorithms work, such as single linkage with dynamic programming at the end to find the minimum cost pruning of $k$ clusters. However, our algorithm is able to recognize optimal clusters locally (without a complete view of the point set). Consider a ball of radius $r^{*}$ around a center $c_{i}$. By Property 2, such a ball exactly captures $C_{i}^{\prime}$. Furthermore, by Property 1, any point in this ball is closer to the center than to points outside of the ball. Is this true for a ball of radius $r^{*}$ around a general point $p$? Not necessarily. If this ball contains a point $q\in C_{j}^{\prime}$ from a different cluster, then $q$ will be closer to a point outside the ball than to $p$ (namely, $c_{j}$, which is guaranteed to be outside of the ball by Property 2). This allows us to determine that the center of such a ball must not be an optimal center.

This structure motivates our Algorithm 1 for asymmetric $k$-center under 2-perturbation resilience. At a high level, we start by constructing the set $A$ (which can be done easily in polynomial time). Then we create the set of all balls of radius $r^{*}$ around all points in $A$ (if $r^{*}$ is not known, we can use a guess-and-check wrapper). Next, we prune this set by throwing out any ball that contains a point farther from its center than to a point outside the ball. We also throw out any ball that is a subset of another one. Our claim is that the remaining balls are exactly $C_{1}^{\prime},\dots,C_{k}^{\prime}$. Finally, we add the points in $S\setminus A$ to their closest point in $A$.

Properties 1 and 2 hold for asymmetric $k$-center instances satisfying 2-perturbation resilience.

Property 1: Assume false, $d(q,p)\leq d(c_{i},p)$. The idea will be that since $q$ is in $A$, it is close to its own center, so we can construct a perturbation in which $q$ replaces its center $c_{j}$. Then $p$ will join $q$’s cluster, causing a contradiction. Construct the following $d^{\prime}$:

Property 2: Assume on the contrary that there exists $q\in C_{j}$, $i\neq j$ such that $d(q,c_{i})\leq r^{*}$. Now we will define a $d^{\prime}$ in which $q$ can become a center for $C_{i}$.

The set $A$ respects the structure of $\mathcal{OPT}$.

From Lemma 3.3, we can use Property 2 in our analysis. First we show that $c_{i}\in A$ for all $i\in[k]$. Given $c_{i}$, $\forall p\in C_{i}$, then $d(c_{i},p)\leq r^{*}$ by definition of $\mathcal{OPT}$. $\forall q\notin C_{i}$, then by Property 2, $d(q,c_{i})>r^{*}$. It follows that for any point $p\in S$, it cannot be the case that $d(p,c_{i})\leq r^{*}$ and $d(c_{i},p)>r^{*}$. Therefore, $c_{i}\in A$.

Now we show that for all $p\in S\setminus A$, if $A(p)\in C_{i}$, then $p\in C_{i}$. Given $p\in S\setminus A$, let $p\in C_{i}$ and assume towards contradiction that $q=A(p)\in C_{j}$ for some $i\neq j$. We will construct a 2-perturbation $d^{\prime}$ in which $q$ replaces $c_{j}$ as the center for $C_{j}$ and $p$ switches from $C_{i}$ to $C_{j}$, causing a contradiction. We construct $d^{\prime}$ as follows. All distances are increased by a factor of $2$ except for $d(q,p)$ and $d(q,q^{\prime})$ for all $q^{\prime}\in C_{j}$. These distances are increased by a factor of $2$ up to $2r^{*}$. Formally,

Now we are ready to show Algorithm 1 returns the optimal clustering.

Algorithm 1 returns the exact solution for asymmetric $k$-center under 2-perturbation resilience.

In this proof, we refer to the first line of Prune balls in Algorithm 1 as Pruning step 1 and the second line as Pruning step 2. First we must show that after Pruning step 2, the remaining sets are exactly $C_{1}^{\prime},\dots,C_{k}^{\prime}=C_{1}\cap A,\dots,C_{k}\cap A$. We prove this in three steps: the sets $G_{c_{i}}$ correspond to $C_{i}^{\prime}$, these sets are not thrown out in Pruning step 1 and Pruning step 2, and all other sets are thrown out in steps Pruning step 1 and Pruning step 2. Because of Lemma 3.3, we can use Properties 1 and 2.

For all $i$, $G_{c_{i}}=C_{i}^{\prime}$: From Lemma 3.4, all centers are in $A$, so $G_{c_{i}}$ will be created in step 2. For all $p\in C_{i}$, $d(c_{i},p)\leq r^{*}$. For all $q\notin C_{i}^{\prime}$, then by Property 2, $d(q,c_{i})>r^{*}$ (and since $c_{i},q\in A$, $d(c_{i},q)>r^{*}$ as well). For all $i$, $G_{c_{i}}$ is not thrown out in step Pruning step 1: Given $s\in G_{c_{i}}$ and $t\notin G_{c_{i}}$. Then $s\in C_{i}^{\prime}$ and $t\in C_{j}^{\prime}$ for $j\neq i$. If $d(t,s)<d(c_{i},s)$, then we get a contradiction from Property 1. For all non-centers $p$, $G_{p}$ is thrown out in Pruning step 1 or Pruning step 2: From the previous paragraph, $G_{c_{i}}=C_{i}^{\prime}$. If $G_{p}\subseteq G_{c_{i}}$, then $G_{p}$ will be thrown out in Pruning step 2 (if $G_{p}=G_{c_{i}}$, it does not matter which set we keep, so without loss of generality say that we keep $G_{c_{i}}$). Then if $G_{p}$ is not thrown out in Pruning step 2, $\exists s\in G_{p}\cap C_{j}^{\prime}$, $j\neq i$. If $s=c_{j}$, then $d(p,c_{j})\leq r^{*}$ and we get a contradiction from Property 2. So, we can assume $s$ is a non-center (and that $c_{j}\notin G_{p}$). But $d(c_{j},s)<d(p,s)$ from Property 1, and therefore $G_{p}$ will be thrown out in Pruning step 1. Thus, the remaining sets after Pruning step 2 are exactly $C_{1}^{\prime},\dots,C_{k}^{\prime}$.

Finally, by Lemma 3.4, for each $p\in C_{i}\setminus A$, $A(p)\in C_{i}$, so $p$ will be added to $G_{c_{i}}$. Therefore, the final output is $C_{1},\dots,C_{k}$. ∎

2.2 Hardness of k𝑘k-center under perturbation resilience

In this section, we show NP-hardness for $k$-center under $(2-\delta)$-perturbation resilience. We show that if there exists a polynomial time algorithm which returns the optimal solution for symmetric $k$-center under $(2-\delta)$-perturbation resilience, In fact, our result holds even under the strictly stronger notion of approximation stability (Balcan et al., 2013). then $NP=RP$, even under the condition that the optimal clusters are all size $\geq\frac{n}{2k}$. Because symmetric $k$-center is a special case of asymmetric $k$-center, we have the same hardness results for asymmetric $k$-center. This proves Theorem 3.5 is tight with respect to the level of perturbation resilience assumed.

There is no polynomial time algorithm for finding the optimal $k$-center clustering under $(2-\delta)$-perturbation resilience, even when assuming all optimal clusters are size $\geq\frac{n}{2k}$, unless $NP=RP$.

We show a reduction from a special case of Dominating Set which we call Unambiguous-Balanced-Perfect Dominating Set. Below, we formally define this problem and all intermediate problems. Part of our reduction is based off of the proof of Ben-David and Reyzin (2012), who showed a reduction from a variant of dominating set to the weaker problem of clustering under $(2-\delta)$-center proximity. $\alpha$-center proximity is the property that for all $p\in C_{i}$ and $j\neq i$, $\alpha d(c_{i},p)<d(c_{j},p)$, and it follows from $\alpha$-perturbation resilience. We use four NP-hard problems in a chain of reductions. Here, we define all of these problems up front. We introduce the “balanced” variants of two existing problems.

We are given three disjoint sets $X_{1}$, $X_{2}$, and $X_{3}$ each of size $m$, and a set $T$ such that $t\in T$ is a triple $t=(x_{1},x_{2},x_{3})$ where $x_{1}\in X_{1}$, $x_{2}\in X_{2}$, and $x_{3}\in X_{3}$. The problem is to find a set $M\subseteq T$ of size $m$ which exactly hits all the elements in $X_{1}\cup X_{2}\cup X_{3}$. In other words, for all pairs $(x_{1},x_{2},x_{3}),(y_{1},y_{2},y_{3})\in M$, it is the case that $x_{1}\neq y_{1}$, $x_{2}\neq y_{2}$, and $x_{3}\neq y_{3}$.

This is the 3DM problem $(X_{1},X_{2},X_{3},T)$ with the additional constraint that $2m\leq|T|\leq 3m$, where $|X_{1}|=|X_{2}|=|X_{3}|=m$.

Given a graph $G=(V,E)$ and an integer $k$, the problem is to find a set of vertices $D\subseteq V$ of size $k$ such that for all $v\in V\setminus D$, there exists exactly one $d\in D$ such that $(v,d)\in E$ (then we say $v$ “hits” $d$).

This is the PDS problem $(G,k)$ with the additional assumption that if the graph has $n$ vertices and a dominating set of size $k$ exists, then each vertex in the dominating set hits at least $\frac{n}{2k}$ vertices.

Additionally, each problem has an “Unambiguous” variant, which is the added constraint that the problem has at most one solution. Valiant and Vazirani (1986) showed that Unambiguous-3SAT is hard unless $NP=RP$. To show the Unambiguous version of another problem is hard, one must establish a parsimonious polynomial time reduction from Unambiguous-3SAT to that problem. A parsimonious reduction is one that conserves the number of solutions. For two problems $A$ and $B$, we denote $A\leq_{par}B$ to mean there is a reduction from $A$ to $B$ that is parsimonious and polynomial time. Some common reductions involve 1-to-1 mappings which are easy to verify parsimony, but many other common reductions are not parsimonious. For instance, the standard reduction from 3SAT to 3DM is not parsimonious (Kleinberg and Tardos, 2006), yet there is a more roundabout series of reductions which all use 1-to-1 mappings, and are therefore easy to verify parsimony. In order to prove Theorem 3.6, we start with the claim that Unambiguous-BPDS is hard unless $NP=RP$. We use a parsimonious series of reductions from 3SAT to B3DM to BPDS. All of these reductions are from prior work, yet we verify parsimony and balancedness.

There is no polynomial time algorithm for Unambiguous-BPDS unless $NP=RP$.

We give a parsimonious series of reductions from 3SAT to B3DM to BPDS. Then it follows from the result by Valiant and Vazirani (1986) that there is no polynomial time algorithm for Unambiguous-BPDS unless $NP=RP$.

To show that B3DM is NP-hard, we use the reduction of Dyer and Frieze (1986) who showed that Planar-3DM is NP-hard. While planarity is not important for the purpose of our problems, their reduction from 3SAT has two other nice properties that we crucially use. First, the reduction is parsimonious, as pointed out by Hunt III et al. (1998). Second, given their 3DM instance $X_{1},X_{2},X_{3},T$, each element in $X_{1}\cup X_{2}\cup X_{3}$ appears in either two or three tuples in $T$. (Dyer and Frieze (1986) mention this observation just before their Theorem 2.3.) From this, it follows that $2m\leq|T|\leq 3m$, and so their reduction proves that B3DM is $NP$-hard via a parsimonious reduction from 3SAT.

Next, we reduce B3DM to BPDS using a reduction similar to the reduction by Ben-David and Reyzin (2012). Their reduction maps every element in $X_{1}\cup X_{2}\cup X_{3}\cup T$ to a vertex in $V$, and adds one extra vertex $v$ to $V$. There is an edge from each element $(x_{1},x_{2},x_{3})\in T$ to the corresponding elements $x_{1}\in X_{1}$, $x_{2}\in X_{2}$, and $x_{3}\in X_{3}$. Furthermore, there is an edge from $v$ to every element in $T$. Ben-David and Reyzin (2012) show that if the 3DM instance is a yes instance with matching $M\subseteq T$ then the minimum dominating set is $v\cup M$. Now we will verify this same reduction can be used to reduce B3DM to BPDS. If we start with B3DM, our graph has $|X_{1}|+|X_{2}|+|X_{3}|+|T|+1\leq 6m+1$ vertices since $|T|\leq 3m$, so $n\leq 6m+1$. Also note that in the yes instance, the dominating set is size $m+1$ by construction. Therefore, to verify the reduction to BPDS, we must show that in the yes instance, each node in the dominating set hits $\geq\frac{6m+1}{2(m+1)}$ nodes. Given $t\in M$, $t$ hits 3 nodes in the graph, and $\frac{n}{2(m+1)}\leq\frac{6m+1}{2m+2}\leq 3$. The final node in the dominating set is $v$, and $v$ hits $|T|-m\geq 2m-m=m$ nodes, and $\frac{6m+1}{2(m+1)}\leq m$ when $m\geq 3$. Therefore, the resulting instance is a BPDS instance.

Now we have verified that there exists a parsimonious reduction 3SAT $\leq_{par}$ BPDS, so it follows that there is no polynomial time algorithm for Unambiguous-BPDS unless $NP=RP$. ∎

Now we can prove Theorem 3.6 by giving a reduction from Unambiguous-BPDS to $k$-center clustering under $(2-\delta)$-perturbation resilience, where all clusters are size $\geq\frac{n}{2k}$. We use the same reduction as Ben-David and Reyzin (2012), but we must verify that the resulting instance is $(2-\delta)$-perturbation resilient. Note that our reduction requires the Unambiguous variant while the reduction of Ben-David and Reyzin (2012) does not, since we are reducing to a stronger problem.

From Lemma 3.11, Unambiguous-BPDS is NP-hard unless $NP=RP$. Now for all $\delta>0$, we reduce from Unambiguous-BPDS to $k$-center clustering and show the resulting instance has all cluster sizes $\geq\frac{n}{2k}$ and satisfies $(2-\delta)$-perturbation resilience.

Given an instance of Unambiguous-BPDS, for every $v\in V$, create a point $v\in S$ in the clustering instance. For every edge $(u,v)\in E$, let $d(u,v)=1$, otherwise let $d(u,v)=2$. Since all distances are either $1$ or $2$, the triangle inequality is trivially satisfied. Then a $k$-center solution of cost 1 exists if and only if there exists a dominating set of size $k$.

Since each vertex in the dominating set hits at least $\frac{n}{2k}$ vertices, the resulting clusters will be size at least $\frac{n}{2k}+1$. Additionally, if there exists a dominating set of size $k$, then the corresponding optimal $k$-center clustering has cost 1. Because this dominating set is perfect and unique, any other clustering has cost 2. It follows that the $k$-center instance is $(2-\delta)$-perturbation resilient. ∎

k𝑘k-center under metric perturbation resilience

In this section, we extend the results from Section 3 to the metric perturbation resilience setting (Angelidakis et al., 2017). We first give a generalization of Lemma 2.8 to show that it can be extended to metric perturbation resilience. Then we show how this immediately leads to corollaries of Theorem 3.1 and Theorem 3.5 extended to the metric perturbation resilience setting.

Recall that in the proofs from the previous section, we created $\alpha$-perturbations $d^{\prime}$ by increasing all distances by $\alpha$, except a few distances $d(u,v)\leq\alpha r^{*}$ which we increased to $\min(\alpha d(u,v),\alpha r^{*})$. In this specific type of $\alpha$-perturbation, we used the crucial property that the optimal clustering has cost $\alpha r^{*}$ (Lemma 2.8). However, $d^{\prime}$ may be highly non-metric, so our challenge is arguing that the proof still goes through after taking the metric completion of $d^{\prime}$ (recall the metric completion of $d^{\prime}$ is defined as the shortest path metric on $d^{\prime}$). In the following lemma, we show that Lemma 2.8 remains true after taking the metric completion of the perturbation.

Given $\alpha\geq 1$ and an asymmetric $k$-center clustering instance $(S,d)$ with optimal radius $r^{*}$, let $d^{\prime\prime}$ denote an $\alpha$-perturbation such that for all $u,v$, either $d^{\prime\prime}(u,v)=\min(\alpha r^{*},\alpha d(u,v))$ or $d^{\prime\prime}(u,v)=\alpha d(u,v)$. Let $d^{\prime}$ denote the metric completion of $d^{\prime\prime}$. Then $d^{\prime}$ is an $\alpha$-metric perturbation of $d$, and the optimal cost under $d^{\prime}$ is $\alpha r^{*}$.

By construction, $d^{\prime}(u,v)\leq d^{\prime\prime}(u,v)\leq\alpha d(u,v)$. Since $d$ satisfies the triangle inequality, we have that $d(u,v)\leq d^{\prime}(u,v)$, so $d^{\prime}$ is a valid $\alpha$-metric perturbation of $d$.

Now given $u,v$ such that $d(u,v)\geq r^{*}$, we will prove that $d^{\prime}(u,v)\geq\alpha r^{*}$. By construction, $d^{\prime\prime}(u,v)\geq\alpha r^{*}$. Then since $d^{\prime}$ is the metric completion of $d^{\prime\prime}$, there exists a path $u=u_{0}$–$u_{1}$–$\cdots$–$u_{s-1}$–$u_{s}=v$ such that $d^{\prime}(u,v)=\sum_{i=0}^{s-1}d^{\prime}(u_{i},u_{i+1})$ and for all $0\leq i\leq s-1$, $d^{\prime}(u_{i},u_{i+1})=d^{\prime\prime}(u_{i},u_{i+1})$.

Case 1: there exists an $i$ such that $d^{\prime\prime}(u_{i},u_{i+1})\geq\alpha r^{*}$. Then $d^{\prime}(u,v)\geq\alpha r^{*}$ and we are done.

Case 2: for all $0\leq i\leq s-1$, $d^{\prime\prime}(u_{i},u_{i+1})<\alpha r^{*}$. Then by construction, $d^{\prime}(u_{i},u_{i+1})=d^{\prime\prime}(u_{i},u_{i+1})=\alpha d(u_{i},u_{i+1})$, and so $d^{\prime}(u,v)=\sum_{i=0}^{s-1}d^{\prime}(u_{i},u_{i+1})=\alpha\sum_{i=0}^{s-1}d(u_{i},u_{i+1})\geq\alpha d(u,v)\geq\alpha r^{*}$.

We have proven that for all $u,v$, if $d(u,v)\geq r^{*}$, then $d^{\prime}(u,v)\geq\alpha r^{*}$. Then by Lemma 2.8, the optimal cost under $d^{\prime}$ must be $\alpha r^{*}$. ∎

Recall that metric perturbation resilience states that the optimal solution does not change under any metric perturbation to the input distances. In the proofs of Theorems 3.1 and 3.5, the only perturbations constructed were the type as in Lemma 2.8. Since Lemma 4.1 shows this type of perturbation is indeed a metric, Theorems 3.1 and 3.5 are true even under metric perturbation resilience.

Given a clustering instance $(S,d)$ satisfying $\alpha$-metric perturbation resilience for asymmetric $k$-center, and a set $C$ of $k$ centers which is an $\alpha$-approximation, i.e., $\forall p\in S$, $\exists c\in C$ such that $d(c,p)\leq\alpha r^{*}$, then the Voronoi partition induced by $C$ is the optimal clustering.

Algorithm 1 returns the exact solution for asymmetric $k$-center under 2-metric perturbation resilience.

k𝑘k-center under local perturbation resilience

In this section, we further extend the results from Sections 3 and 4 to the local perturbation resilience setting. First we show that any $\alpha$-approximation to $k$-center will return each optimal $\alpha$-MPR cluster, i.e., Corollary 4.2 holds even in the local perturbation resilience setting. Then for asymmetric $k$-center, we show that a natural modification to the $O(\log^{*}n)$ approximation algorithm of Vishwanathan (1996) leads to an algorithm that maintains its performance in the worst case, while exactly returning each optimal cluster located within a 2-MPR region of the dataset. This generalizes Corollary 4.3.

In section 3, we showed that any $\alpha$-approximation algorithm for $k$-center returns the optimal solution for instances satisfying $\alpha$-perturbation resilience (and this was generalized to metric perturbation resilience in the previous section). In this section, we extend this result to the local perturbation resilience setting. We show that any $\alpha$-approximation will return each (local) $\alpha$-MPR cluster. For example, if a clustering instance is half 2-perturbation resilient, running a 2-approximation algorithm will return the optimal clusters for half the dataset, and a 2-approximation for the other half.

Given an asymmetric $k$-center clustering instance $(S,d)$, a set $C$ of $k$ centers which is an $\alpha$-approximation, and a clustering $\mathcal{C}$ defined as the Voronio partition induced by $C$, then each $\alpha$-MPR cluster is contained in $\mathcal{C}$.

The proof is very similar to the proof of Theorem 3.1. The key difference is that we reason about each perturbation resilient cluster individually, rather than reasoning about the global structure of perturbation resilience.

Given an $\alpha$-approximate solution $\mathcal{C}$ to a clustering instance $(S,d)$, and given an $\alpha$-MPR cluster $C_{i}$, we will create an $\alpha$-perturbation as follows. Define $\mathcal{C}(v):=\text{argmin}_{c\in\mathcal{C}}d(c,v)$. For all $v\in S$, set $d^{\prime\prime}(v,\mathcal{C}(v))=\min\{\alpha r^{*},\alpha d(v,\mathcal{C}(v))\}$. For all other points $u\in S$, set $d^{\prime\prime}(v,u)=\alpha d(v,u)$. Then by Lemma 4.1, the metric completion $d^{\prime}$ of $d^{\prime\prime}$ is an $\alpha$-perturbation of $d$ with optimal cost $\alpha r^{*}$. By construction, the cost of $\mathcal{C}$ is $\leq\alpha r^{*}$ under $d^{\prime}$, therefore, $\mathcal{C}$ is an optimal clustering. Denote the set of centers of $\mathcal{C}$ by $C$. By definition of $\alpha$-MPR, there exists $v_{i}\in C$ such that $\text{Vor}_{C,d^{\prime}}(v_{i})=C_{i}$. Now, given $v\in C_{i}$, $\text{argmin}_{u\in C}d^{\prime}(u,v)=v_{i}$, so by construction, $\text{argmin}_{u\in C}d(u,v)=v_{i}$. Therefore, $\text{Vor}_{C,d}(v_{i})=C_{i}$, so $C_{i}\in\mathcal{C}$.

2 Asymmetric k𝑘k-center

In Section 3, we gave an algorithm which outputs the optimal clustering for asymmetric $k$-center under 2-perturbation resilience (Algorithm 1 and Theorem 3.5), and we extended it to metric perturbation resilience in Section 4. In this section, we extend the result further to the local perturbation resilience setting, and we show how to add a worst-case guarantee of $O(\log^{*}n)$. Specifically, we give a new algorithm, which is a natural modification to the $O(\log^{*}n)$ approximation algorithm of Vishwanathan (1996), and show that it maintains the $O(\log^{*}n)$ guarantee in the worst case while returning each optimal perturbation resilient cluster in its own superset. As a consequence, if the entire clustering instance satisfies 2-metric perturbation resilience, then the output of our algorithm is the optimal clustering.

Given an asymmetric $k$-center clustering instance $(S,d)$ of size $n$ with optimal clustering $\{C_{1},\dots,C_{k}\}$, for each 2-MPR cluster $C_{i}$, there exists a cluster outputted by Algorithm 3 that is a superset of $C_{i}$ and does not contain any other 2-MPR cluster. Formally, given the output clustering $\mathcal{C}^{\prime}$ of Algorithm 3, for all 2-MPR clusters $C_{i}$ and $C_{j}$, there exists $C_{i}^{\prime}\in\mathcal{C}^{\prime}$ such that $C_{i}\subseteq C_{i}^{\prime}$ and $C_{j}\cap C_{i}^{\prime}=\emptyset$. Furthermore, the overall clustering returned by Algorithm 3 is an $O(\log^{*}n)$-approximation.