A bi-criteria approximation algorithm for $k$ Means

Introduction

The $k$-means clustering problem is one of the most popular models for unsupervised Machine Learning. The problem is formally defined as follows.

The most common heuristic for $k$-means is Lloyd’s algorithm introduced in 1957 . Llloyd’s algorithm starts with some initial solution and then iteratively improves it by alternating two steps: at the first step, the algorithm picks the optimal clustering for the current set of centers; at the second step, the algorithm picks the optimal set of centers for the current clustering. While we know that the algorithm performs well on well-clusterable data it performs arbitrarily badly on general instances. There exist many variants of this algorithm and many heuristics for picking the initial solution. Unfortunately, none of them give a constant (not depending on $k$) factor approximation. One of the most popular ones is the $k$-means++ algorithm that has an $O(\log k)$-approximation factor .

The general $k$-means clustering problem has recently been shown to be APX-hard, ruling out a PTAS in the general case . However, a variety of PTASes exist for special cases of the problem. Inaba, Katoh, and Imai gave a $(1+\varepsilon)$-approximation algorithm for the case in which the number of clusters, $k$, and the dimension of the space, $d$, are fixed. Since then many more PTASes were proposed for other special cases. Additionally, there are many results showing the NP-hardness for several special cases .

The best constant factor approximation algorithm for the general case of the problem was proposed by a decade ago. Their algorithm gives $9+\varepsilon$ factor approximation. Using the connection with $k$-median problem designed an alternative constant factor approximation algorithm. showed that running the $k$-means++ algorithm for more steps gives an $\alpha=4+\varepsilon$ factor approximation by opening $\lceil 16(k+\sqrt{k})\rceil$ centers, and also showed how to modify the resulting solution to obtain a set of $k$ centers attaining an $O(1)$ factor guarantee.

In most practical applications the target number $k$ of clusters is not fixed in advance, rather we would like to find a number $k$ that provides a well-clusterable solution. Here, we show how to substantially improve the approximation factor by slightly violating the constraint on the number of clusters. We present bi-criteria approximation algorithms for the general case of the problem. A $(\beta,\alpha)$ bi-criteria approximation algorithm finds a solution with $\beta k$ clusters, whose cost is at most $\alpha$ times the optimal cost of a solution using $k$ clusters. In contrast to the approach of , our algorithms find an approximate solution for every $\beta>1$. Our approximation is always at most $9$, and decreases rapidly with $\beta$. In particular, we obtain a $4$-approximation by opening only $1.65k$ centers, improving over previous results by a factor of nearly 10, and obtain improved approximation factors $\alpha(\beta)$ as $\beta$ continues to grow. For example, $\alpha(1.3)<6.45$, $\alpha(1.5)<4.8$; $\alpha(2)<2.59$, and $\alpha(3)<1.4$. In general, we argue that in many applications the number of clusters is not important as long as it approximately equals $k$. For these applications we can obtain an approximation factor very close to 1.

We give three bi-criteria algorithms—two based on linear programming and one based on local search. We show the algorithms’ approximation factors as a function of $\beta$ in Figure 1. Note that our linear programming algorithm attains a better approximation $\alpha$ for large $\beta$, while the local search algorithm is better for $\beta$ near 1.

In the $k$-median problem, we are given a set of points $\cal D$, a set of potential center locations ${\cal C}$ and a distance function $(d(i,j))_{i\in{\cal{C}},j\in{\cal{D}}}$. The cost of assigning point $j$ to center $i$ is $d(i,j)$. Our goal is to open at most $k$ centers and assign each point to a center so as to minimize the total cost.

The first approximation algorithms for the $k$-median problem were given by , who gave an LP-rounding algorithm that attains an approximation factor of $1+\varepsilon$ by opening $O(k\ln n)$ centers (i.e. a $(1+\epsilon,O(\ln n))$ bi-criteria approximation). In further work, showed that if the distance function $d$ is a metric, it is possible to obtain a $2(1+\varepsilon)$ approximation algorithm by opening only $(1+1/\varepsilon)k$ centers. The first constant-factor approximation for the metric $k$-median problem using only $k$ centers was obtained by , who showed that a simple local search algorithm gives a $3+\varepsilon$ approximation. This remained the state of the art, until recently, when gave a $2.732+\varepsilon$ approximation algorithm based on LP rounding. Subsequently, this has been improved to $2.611+\varepsilon$ by .

We give three approximation algorithms. The first algorithm is based on linear programming. It gives

approximation (see also (11) for a slightly tighter bound). The second algorithm is based on local search. It gives

approximation. The third algorithm is also based on linear programming. It gives

approximation. The algorithm is similar to the first algorithm, but it uses pipage rounding (see ) instead of randomized rounding. In the conference version of the paper, we omit the description of the third algorithm. The approximation factors are shown in Figure 1.

In Section 2 we introduce the notation that we shall use throughout the rest of the paper and review standard notions related to both the $k$-means and $k$-median problems. In Section 3, we give the details of our reduction to $k$-median. Finally, in Sections 4 and 5, respectively, we present our main LP-based algorithm and local search algorithm for the resulting $k$-median instances.

Preliminaries

We now fix some notation, and recall some basic properties of $k$-means solutions and the standard linear program for the $k$-median problem. Additionally, we define the notion of an $\alpha$-relaxed 3-hop triangle inequality, which will be crucial to the analysis of our LP-rounding algorithms.

Note that to describe an optimal solution to the $k$-means problem, it is sufficient to specify either all clusters or all centers in the solution. Indeed, given a list of clusters $S_{1},\dots,S_{k}$, we can find the optimal assignment of centers $c_{i}$ for it: the optimal choice of center $c_{i}$ for $S_{i}$ is $\frac{1}{|S_{i}|}\sum_{x_{j}\in S_{i}}x_{j}$. For this choice of $c_{i}$, we have

Given a partition $S=\left\langle S_{1},\ldots,S_{k}\right\rangle$ of $X$ into clusters, we then denote by $\operatorname{cost}_{X}(S)$ the cost of this optimal choice of centers. That is,

Similarly, given a list $C$ of centers $c_{1},\dots,c_{k}$, we can find the optimal partition $S=\left\langle S_{1},\ldots,S_{k}\right\rangle$ of $X$ into clusters. For each $c\in C$, let $N_{C}(c)$ be the set of those points $x\in X$ that are closer to $c_{i}$ than to other centers $c_{j}\neq c_{i}$ (if a point $x$ is at the same distance from several centers, we break the ties arbitrarily). The optimal partition for $C$ then sets $S_{i}=N_{C}(c_{i})$. Given a set $C$ of $k$ centers, we define $\operatorname{cost}_{X}(C)\equiv\operatorname{cost}_{X}(T)$, where $T=\left\langle N_{C}(c_{1}),\ldots,N_{C}(c_{k})\right\rangle$ is the partition induced by $C$.

2 k𝑘k-median

We will reduce a given instance $X$ of $k$-means problem to an instance of the $k$-median problem, specified by $\langle{\cal{D}},{\cal{C}},d\rangle$. By analogy with $k$-means problem, we can consider a partition $S=S_{1},\ldots,S_{k}$ of demand points from ${\cal{D}}$, and then consider the best choice of a single center for each partition. We denote the cost of this choice by $\operatorname{cost}_{{\cal{D}},d}(S)$:

Similarly, given a list of $k$ centers $C=\left\langle c_{1},\ldots,c_{k}\right\rangle$, let $N_{C}(c_{i})$ be the set of those demand points $x\in{\cal{D}}$ that are closer (according to the distance function $d$) to $c_{i}$ than to any other center in $C$ (again, if a point $x$ is at the same distance from several facilities, we break ties arbitrarily). As in the case of $k$-means, we define $\operatorname{cost}_{{\cal{D}},d}(C)\equiv\operatorname{cost}_{{\cal{D}},d}(T)$ where $T=\left\langle N_{C}(c_{1}),\ldots,N_{C}(c_{k})\right\rangle$ is the partition of ${\cal{D}}$ induced by $C$.

Although the distance function $d$ in our $k$-median instances will not satisfy the standard triangle inequality, we can show that it satisfies a relaxed variant of the following sort:

We say that $d$ satisfies an $\alpha$-relaxed $3$-hop triangle inequality on ${\cal{D}}\cup{\cal{C}}$ if, for any $j,j^{\prime}\in{\cal{D}}$ and $i,i^{\prime}\in{\cal{C}}$, we have

Specifically, we shall show that the distances produced by our reduction satisfy a $3$-relaxed $3$-hop triangle inequality.

Reduction from k𝑘k-means to k𝑘k-median

We now give the details of our reduction from the $k$-means to the $k$-median problem. In the $k$-median problem, a finite set ${\cal{C}}$ of candidate centers is specified, while in the $k$-means problem, the ideal center for each cluster $S_{i}$ of points is given by the centroid of $S_{i}$. Ideally, we want to ensure that for every possible centroid of the original $k$-means instance, there is some nearby candidate centers in ${\cal{C}}$. The following notion of an $\varepsilon$-approximate centroid set, introduced by , captures this requirement.

Observe that if ${\cal{C}}$ is an $\varepsilon$-approximate centroid set for $X$, then for every set of $k$ centers $C$ (in particular, for the optimal set $C^{*}$), there exists a $k$-point subset $\widetilde{C}\subset{\cal{C}}$ such that

Thus, if we restrict our search for $k$ center points in $k$-means problem to only those points of ${\cal{C}}$, we lose at most a factor of $(1+\varepsilon)$.

Unfortunately, in our setting, the dimension $p$ of the space in which points $x_{1},\dots,x_{n}$ lie may be as large as $n$. Thus, in order to apply Theorem 5, we first embed $X$ into a low-dimensional space using the Johnson–Lindenstrauss transform.

We say that the map $\varphi$ is a dimension reduction transform for $X$.

1. For every $\varepsilon\in(0,1/2)$, there exists a polynomial-time reduction from $k$-means to $k$-median with distance function that satisfies the 3-relaxed 3-hop triangle inequality. Specifically, given an instance $X$ of $k$-means, the reduction outputs an instance $\langle{\cal{D}},{\cal{C}},d\rangle$ of $k$-median with $|{\cal{D}}|=|X|$, $|{\cal{C}}|=n^{O(\log(1/\varepsilon)/\varepsilon^{2})}$, and distance $d$ that satisfies the 3-relaxed 3-hop triangle inequality such that

where $S=\left\langle S_{1},\ldots,S_{k}\right\rangle$ is a partition of ${\cal{D}}$ and $\psi(S)=\left\langle\psi(S_{1}),\ldots,\psi(S_{k})\right\rangle$ is the corresponding partition of $X$. The reduction runs in time $n^{O(\log(1/\varepsilon)/\varepsilon^{2})}$.

Algorithm for k𝑘k-Median with Relaxed Triangle Inequality

We now turn to the problem of approximating the $k$-median instance from Theorem 7. Our first algorithm is based on the following standard linear programming relaxation for the $k$-median problem:

In the integral solution, each variable $y_{c}$ indicates whether the center $c$ is open; and each variable $z_{xc}$ indicates whether the point $x$ is assigned to the center $c$. Constraint (4) asserts that we should open exactly $k$ centers; constraint (5) ensures that every point is assigned to exactly one center; finally, constraint (6) says that points can be assigned only to open centers. In a fractional LP solution, all $z_{xc}$ and $y_{c}$ lie in the interval $$. Note that in the integral solution,$z_{xc}=y_{c}$, if$z_{xc}>0$(as both$z_{xc}$and$y_{c}$must be equal to$1$). We can slightly change any feasible LP solution so it also satisfies this property. Specifically, we split any center$c$which does not satisfy$y_{c}=z_{xc}$(for some$x\in X$) in two co-located centers$c_{1}$and$c_{2}$: one with weight$z_{xc}$and the other with weight$y_{c}-z_{xc}$. We distribute the weights$z_{x^{\prime}c}$among them as follows: we let$z_{x^{\prime}c_{1}}=\min(z_{x^{\prime}c},y_{c_{1}})$;$z_{x^{\prime}c_{2}}=y_{c_{2}}-\min(z_{x^{\prime}c},y_{c_{1}})$. Note that this is a standard assumption in the$k$-median literature. We refer the reader to (see Lemma 1) and for more details. The values$y_{c}$define the measure$y$on${\cal{C}}$:$y(C)=\sum_{c\in C}y_{c}$. In the rounding algorithm and in the analysis, it will be convenient to think of this measure as of “continuous measure”: That is, if needed we will split the centers into co-located centers to ensure that we can find a set of any given measure$\mu$.

For every point $x\in X$, let $C_{x}=\{c\in{\cal{C}}:z_{xc}>0\}$. The set $C_{x}$ contains all centers that serve $x$ in the LP solution. Recall that we modify the solution so that $y_{c}=z_{xc}$ if $z_{xc}>0$. Hence, $y_{c}=z_{xc}$ if $x\in C_{x}$. For every point $x\in X$, we define its LP radius $R_{x}$ as:

Observe, that the LP value, which we denote by $LP$, equals $\sum_{x\in X}R_{x}$.

Algorithm. We now describe our LP-rounding algorithm for $k$-Medians with relaxed $3$-hop triangle inequality.

There exists a $(\beta,\alpha)$ bi-criteria approximation algorithm for $k$-means with

The algorithm first solves the LP problem and modifies the LP solution as described above if necessary. Then, it partitions all centers into $\beta k$ groups $Z\in{\cal{Z}}$, each with LP measure $1/\beta$. It picks one center $c$ at random from each group $Z$ with probability $\beta y_{c}$ (note, that $\sum_{c\in Z}\beta y_{c}=1$). The algorithm outputs the set of $\beta k$ chosen centers, and assigns every point to the closest center.

We now describe the construction of ${\cal{Z}}$ in more detail. We partition centers into $\beta k$ groups as follows. For every $x\in X$, we find the unique ball $B_{x}$ around $x$ whose LP weight exactly equals $1/\beta$ (To do so, we may split some centers, and pick some centers in $B_{x}$ at the boundary of the ball but not the others). We find a subset of points ${\cal{W}}$ such that balls $B_{x}$ with $x\in{\cal{W}}$ are disjoint, and for every point $x\in X$, we also define a “witness” $w(x)\in{\cal{W}}$. To this end, we sort all points $x\in X$ by the LP radius $R_{x}$ in the ascending order, and then consider them one by one. For each $x\in X$, if $B_{x}$ is disjoint from all previously chosen balls, then we add $x$ to the set ${\cal{W}}$, we set $w(x)=x$. Otherwise, if $B_{x}$ intersects some other ball $B_{x^{\prime}}$ that is already chosen, we discard $B_{x}$ and set $w(x)=x^{\prime}$. If there are several balls $B_{x^{\prime}}$ intersecting $B_{x}$, we pick the first $x^{\prime}$ according to our ordering as the witness. Note, that $R_{w(x)}\leq R_{x}$ for all $x$. Once, we found a disjoint collection of balls $\{B_{x}:x\in{\cal W}\}$, we add them to the set ${\cal{Z}}$. We partition centers not covered by $\cup_{x\in{\cal{W}}}B_{x}$ into groups of LP weight $1/\beta$ arbitrarily and add these groups to ${\cal{Z}}$. Thus, we obtain a partitioning ${\cal{Z}}$ of all centers into groups of LP weight $1/\beta$.

Analysis. We show that the algorithm returns a valid solution, and then prove an upper bound on its expected cost. The algorithm picks exactly one vertex from each group, so it always picks $\beta k$ vertices. Hence, it always outputs a valid solution.

Fix $x\in X$. Recall, that $C_{x}=\{c:z_{xc}>0\}$ is the set of all centers that serve $x$ in the LP solution. We upper bound $d(x,S)$ by $d(x,(C_{x}\cup B_{w(x)})\cap S)$, which is the distance to the closest center in $C_{x}\cup B_{w(x)}$ chosen by the algorithm. Note that the solution $S$ always contains at least one center in $B_{w(x)}$, so $(C_{x}\cup B_{w(x)})\cap S\neq\varnothing$. For the proof, we pick a particular (random) center $f(x)\in(C_{x}\cup B_{w(x)})\cap S$.

We define $f(x)$ using the following randomized procedure. Consider the partitioning ${\cal{Z}}$ of all centers into groups of measure $1/\beta$ used by the algorithm. Let $\widetilde{\cal{Z}}=\{Z\cap C_{x}:Z\in{\cal{Z}};\,Z\cap C_{x}\neq\varnothing\}$ be the induced partitioning of the set $C_{x}$. For all $\widetilde{Z}\in\widetilde{{\cal{Z}}}$ we independently flip a coin and with probability $(1-e^{-\beta y(\widetilde{Z})})/(\beta y(\widetilde{Z}))$ make the set $\widetilde{Z}$ active. We let $A\subset C_{x}$ to be the union of all active sets $\widetilde{Z}$; we say that centers in $A$ are active centers. Let $f(x)$ be the center in $A\cap S$ closest to $x$, if $A\cap S\neq\varnothing$ ; let $f(x)$ to be the unique center in $B_{w(x)}\cap S$, otherwise. We set ${\cal{E}}=0$, if $A\cap S\neq\varnothing$; and ${\cal{E}}=1$, otherwise. Roughly speaking, ${\cal{E}}$ indicates whether $f(x)\in C_{x}$ or $f(x)\in B_{w(x)}$: Specifically, if ${\cal{E}}=0$, then $f(x)\in C_{x}$; if ${\cal{E}}=1$, then $f(x)\in B_{w(x)}$. Note, however, that $C_{x}\cap B_{w(x)}\neq\varnothing$, and $f(x)$ may belong to $C_{x}\cap B_{w(x)}$.

The center $f(x)$ may not be the closest to $x$, but since $f(x)\in S$, we have

In Lemma 9, we show that $\Pr({\cal{E}}=0)=1-e^{-\beta}$. Thus,

We bound the expected distance from $x$ to $f(x)$ given ${\cal{E}}=0$ in Lemma 10. We show that

Here, we used that $R^{\beta}_{x}$ is the radius of $B_{x}$; $R^{\beta}_{w(x)}$ is the radius of $B_{w(x)}$. By the Markov inequality, $R^{\beta}_{x}\leq\beta R_{x}/(\beta-1)$ (see Lemma 15). In Lemma 14,we show that there exists two nonnegative numbers $r_{1}$ and $r_{2}$ ($r_{1}\leq r_{2}$) such that

where $\gamma$ is some parameter in $$. Hence,

Combining all bounds above we get the following inequality:

This function can be upper bounded by $\alpha(\beta)$ defined in (8). We conclude that the approximation factor of the algorithm is upper bounded by $\alpha(\beta)$.

We now bound $E[d(x,f(x))\mid{\cal{E}}=0]$.

We have $E[d(x,f(x))\mid{\cal{E}}=0]\leq R_{x}$.

We define two sets of random variables $P$ and $Q$, and then show that they are identically distributed. If the algorithm picks a center $c$ in $\widetilde{Z}$, and $\widetilde{Z}$ is active, let $P(\widetilde{Z})=c$. Let $P(\widetilde{Z})=\perp$, otherwise. The random variables $P(\widetilde{Z})$ are mutually independent for all $\widetilde{Z}\in\widetilde{{\cal{Z}}}$; and

To define $Q$, we introduce an auxiliary Poisson arrival process. At every point of time $t\in[0,\beta]$, we pick a center $c\in C_{x}$ with probability $y_{c}dt$ (i.e., with arrival rate $y_{c}$). For every $\widetilde{Z}$, let $Q(\widetilde{Z})$ be the first center chosen in $\widetilde{Z}$. If no centers in $\widetilde{Z}$ are chosen, we let $Q(\widetilde{Z})=\perp$. Note that we pick two centers at exactly the same time with probability , hence $Q(\widetilde{Z})$ is well defined. Conditional on $Q(\widetilde{Z})\neq\perp$, the random variable $Q(\widetilde{Z})$ is uniformly distributed in $\widetilde{Z}$ with respect to LP weights $y_{c}$ (since at every given time $t$, the probability of arrival equals $y_{c}dt$). Then, $\Pr(Q(\widetilde{Z})\neq\perp)=(1-e^{-\beta y(\widetilde{Z})})$. Hence, $\Pr(Q(\widetilde{Z})=c)=(1-e^{-\beta y(\widetilde{Z})})y_{c}/y(\widetilde{Z})$. Note that all random variables $Q$ are mutually independent. Thus, the random variables $Q$ have the same distribution as random variables $P$.

Note that if ${\cal{E}}=0$, then $f(x)$ is the closest center in $\{P(\widetilde{Z}):\widetilde{Z}\in\widetilde{{\cal{Z}}};\widetilde{Z}\neq\perp\}$ to $x$. If ${\cal{E}}=1$, then all $P(\widetilde{Z})$ are equal to $\perp$. Let $U_{Q}=\{Q(\widetilde{Z}):\widetilde{Z}\in\widetilde{{\cal{Z}}};\widetilde{Q}\neq\perp\}$. Since $P$ and $Q$ have the same distribution, we have

Let $D_{x}=B_{w(x)}\cap C_{x}$ and $\gamma=\beta y(D_{x})$. Note that $\gamma\in$, since $y(B_{w(x)})=1/\beta$. We find $\Pr(f(x)\in D_{x}\mid{\cal{E}}=1)$.

Observe that the set $D_{x}=B_{w(x)}\cap C_{x}$ is one of the sets in the partitioning $\widetilde{\cal{Z}}$ as $w(x)\in{\cal{W}}$ and $B_{w(x)}\in{\cal{Z}}$. Assume $f(x)\in D_{x}$ and ${\cal{E}}=1$. Since $f(x)\in D_{x}$, we have $S\cap D_{x}\neq\varnothing$. Thus, $D_{x}$ must be inactive (otherwise, ${\cal{E}}$ would be ). Moreover, for every $\widetilde{Z}\neq D_{x}$ ($\widetilde{Z}\in{\cal{Z}}$), $\widetilde{Z}$ is inactive or $\widetilde{Z}\cap S=\varnothing$ (again, otherwise, ${\cal{E}}$ would be ). Hence, the event $\{f(x)\in D_{x}\text{ and }{\cal{E}}=1\}$ can be represented as the intersection of the following three independent events: $\{S\cap D_{x}\neq\varnothing\}$, $\{D_{x}\text{ is not active}\}$, and $\{\text{there are no active vertices in }(C_{x}\setminus D_{x})\cap S\}$. The probability of the first event is $\beta y(D_{x})$; the probability of the second event is $1-(1-e^{-\beta y(D_{x})})/(\beta y(D_{x}))$; the probability of the third event is $e^{-\beta y(C_{x}\setminus D_{x})}$ (this probability is computed as in Lemma 9). Thus,

Local Search

Unfortunately the analyses of relies heavily on the triangle inequality, while the instances generated by Theorem 7 satisfy only a 3-relaxed 3-hop triangle inequality. Thus, we proceed as in .

Let $O=\left\langle o_{1},\ldots,o_{k}\right\rangle$ be an optimal set of $k$ centers, and $A=\left\langle a_{1},\ldots,a_{\beta k}\right\rangle$ be the set of $\beta k$ centers produced by the local search algorithm. As in , we say that a center $a\in A$ captures a center $o\in O$ if $a$ is the center of $A$ that is closest to $o$. Note that each center in $A$ can potentially capture several centers in $O$, but each center in $O$ is captured by exactly one center of $A$. We now construct a set of local swaps to consider in our analysis. We say that a center in $A$ is “good” if it does not capture any center of $O$. Then, because each center of $O$ is captured by only one center of $A$, we must have at least $\beta k-k=(\beta-1)k$ good centers in $A$. We fix some such set of $(\beta-1)k$ good centers; we call them “auxiliary” centers and set them aside for now.

For the remaining $k$ centers $B\subseteq A$, we proceed exactly as in : we assign each center in $O$ to the bad center of $B$ that captures it. This creates a partition $O_{1},\ldots,O_{r}$ of centers in $O$. We similarly partition the centers of $B$ into $r$ parts $B_{1},\ldots,B_{r}$ with $|B_{i}|=|O_{i}|$; for each $1\leq i\leq r$, let $B_{i}$ contain the bad center of $B$ that captures all of $O_{i}$ together with $|B_{i}|-1$ unique good centers of $B$. Note that the fact that each center of $O$ is captured only once ensures that there are indeed enough good centers in $B$ for our construction. Now, we use this partition of $B$ and $O$ to construct a set of swaps, each assigned some weight. If $|O_{i}|\leq p$, we consider the $\langle B_{i},O_{i}\rangle$ with weight 1. If $|O_{i}|=q>p$, we consider a group of singleton swaps $\langle\{b\},\{o\}\rangle$, where $o\in O_{i}$ and $b$ is a good center in $B_{i}$, each with weight $\frac{1}{q-1}$. At this point, note that every center in $O$ occurs in swaps of total weight $1$, and every center in $B$ occurs in swaps of total weight at most $\frac{q}{q-1}\leq 1+\frac{1}{p}$. Now, we add swaps involving auxiliary centers; for each of the $(\beta-1)k$ auxiliary centers $a\in A\setminus B$ and each $o\in O$, we consider singleton swap $\langle\{a\},\{o\}\rangle$, assigned weight $\frac{1}{k}$. Each center of $O$ now occurs in swaps of total weight $1+(\beta-1)=\beta$, while each center of $A\setminus B$ occurs in swaps of total weight $1$.

Summarizing, our set of swaps satisfies the following properties: (1) each center of $O$ occurs in swaps of total weight $\beta$; (2) each center of $A$ occurs in swaps of total weight at most $1+\frac{1}{p}$; (3) for any swap $\langle A^{\prime},O^{\prime}\rangle$ in our set, no center in $A^{\prime}$ captures any center not in $O^{\prime}$. We now give a brief sketch of how these properties lead to our desired approximation ratio (we give a full description of the analysis in the appendix). Our analysis closely follows that of .

As in , the total change $\operatorname{cost}_{{\cal{D}},d}(A\setminus A^{\prime}\cup O^{\prime})-\operatorname{cost}_{{\cal{D}},d}(A)$ due to performing a single swap $\langle A^{\prime},O^{\prime}\rangle$ is at most:

If $A$ is locally optimal, then we must have that $\operatorname{cost}_{{\cal{D}},d}(A\setminus A^{\prime}\cup O^{\prime})-\operatorname{cost}_{{\cal{D}},d}(A)\geq 0$ for all swaps $(A^{\prime},O^{\prime})$ considered by the algorithm. In particular, for each swap $\langle A^{\prime},O^{\prime}\rangle$ in our set, we have:

Multiplying each inequality (12) by the weight of its swap and then adding the resulting inequalities we obtain:

due to properties (1) and (2) of our set of swaps. Theorem 7 part 2, which shows that our center set is an approximate $k$-means centroid set, then allows us to simplify the final term above as in , giving:

where $\alpha^{2}=\frac{\operatorname{cost}_{{\cal{D}},d}(A)}{\operatorname{cost}_{{\cal{D}},d}(O)}$ is the squared approximation ratio of our algorithm. Rearranging and simplifying (again, we give a detailed analysis in the appendix), we obtain.

Therefore, we have proved the following theorem:

There exists an algorithm that produces a solution for any instance of $\beta k$-median problem satisfying the properties of Theorem 7, where $\beta>1$ is a fixed constant. For any $p\geq 1$ and any $\varepsilon\in(0,1]$, the algorithm runs in time polynomial in $|{\cal{C}}\cup{\cal{D}}|$ and produces a solution $A$ satisfying:

where $O$ is the optimal set of $k$ centers in $\cal C$.

References

Appendix A Detailed Analysis of the LP Rounding Algorithm

Given $f(x)\in D_{x}$ and ${\cal{E}}=1$, the random center $f(x)$ is distributed uniformly in $D_{x}$ (with respect to the LP weights $y$). Hence, $\Pr(f(x)=c)=y_{c}/y(D_{x})$ for $c\in D_{x}$. We have

There exists two nonnegative numbers $r_{1}$ and $r_{2}$ satisfying

Denote the expected distance from a random center $c$ in $B_{w(x)}\setminus D_{x}$ to $w(x)$ by $r_{1}$ and distance from a random center $c$ in $C_{w(x)}\setminus B_{w(x)}$ to $w(x)$ by $r_{2}$:

The following inequality holds: $R_{x}^{\beta}\leq\beta R_{x}/(\beta-1)$.

Every center $c\in C_{x}\setminus B_{x}$ is at distance at least $R^{\beta}_{x}$ from $x$. Hence,

Appendix B Detailed Analysis of the Local Search Algorithm

Here we give a detailed analysis of the local search algorithm from section 5, closely following .

Let $\langle\rho_{i}\rangle$ and $\langle\xi_{i}\rangle$ be two sequences of reals such that $\alpha^{2}=(\sum_{i}\rho_{i}^{2})/(\sum_{i}\xi_{i}^{2})$ for some $\alpha>0$. Then,

We now show how local optimality implies the desired inequality. For a demand point $x\in{\cal{D}}$, let $a_{x}$ and $o_{x}$ denote the closest facility to $x$ in $A$ and $O$, respectively. Recall that for for $a\in A$, $N_{A}(a)$ is precisely the set of all those demand points $x\in{\cal{D}}$ such that $a_{x}=a$, and, similarly, for $o\in O$, $N_{O}(o)$ is the set of all demand point $x\in{\cal{D}}$ such that $o_{x}=o$. Now, we upper bound the change in cost due to some swap $\langle A^{\prime},O^{\prime}\rangle$ in our set of swaps. We do this by constructing a feasible assignment of all points in ${\cal{D}}$ to centers in $A\setminus A^{\prime}\cup O^{\prime}$. For each $o\in O^{\prime}$, we assign all the points in $N_{O}(o)$ to $o$. This changes the cost by

Now, fix a point $x\in N_{A}(A^{\prime})\setminus N_{O}(O^{\prime})$, and consider $x$’s closest optimal center $o_{x}$. We must have $o_{x}\not\in O^{\prime}$. Let $a_{o_{x}}$ be the closest center to $o_{x}$ in $A$. Then, by property (3) above, $a_{o_{x}}\not\in A^{\prime}$, since $a_{o_{x}}$ captures $o_{x}$ but $o_{x}\not\in O^{\prime}$. We reassign $x$ to $a_{o_{x}}$. The total cost of reassigning all such points $x$ is at most:

where the inequality follows from the fact that $a_{x}$ is the closest center to $x$ in $A$, and so $d(x,a_{o_{x}})-d(x,a_{x})\geq 0$ for all $x\in N_{A}(A^{\prime})\cap N_{O}(O^{\prime})$. Thus, the total change $\operatorname{cost}_{{\cal{D}},d}(A\setminus A^{\prime}\cup O^{\prime})-\operatorname{cost}_{{\cal{D}},d}(A)$ for each swap $\langle A^{\prime},O^{\prime}\rangle$ is at most:

If $A$ is locally optimal, then we must have that $\operatorname{cost}_{{\cal{D}},d}(A\setminus A^{\prime}\cup O^{\prime})-\operatorname{cost}_{{\cal{D}},d}(A)\geq 0$ for all swaps $(A^{\prime},O^{\prime})$ considered by the algorithm. In particular, for each swap $\langle A^{\prime},O^{\prime}\rangle$ in our set, we have:

Set $\gamma=1+\frac{1}{p}$. Then, multiplying each such inequality by the weight of its swap and then adding the resulting inequalities we obtain

where we have exploited properties (1) and (2) of our set of swaps to bound the number of times a given center in $O$ or $A$ is counted in our sum of inequalities.

It remains to bound the final term in (13). Consider some $o\in O$, and let $c$ be the centroid of $N_{O}(o)$. As above, we will let $a_{o}$ denote the closest center in $A$ to $O$. Then, note that:

Let $\alpha^{2}=\frac{\operatorname{cost}_{{\cal{D}},d}(A)}{\operatorname{cost}_{{\cal{D}},d}(O)}=\frac{\sum_{x\in{\cal{D}}}d(x,a_{x})}{\sum_{x\in{\cal{D}}}d(x,o_{x})}$ be the approximation ratio attained by the algorithm. Summing over all $o\in O$, and recalling that for all $x\in N_{O}(o)$ we have $o_{x}=o$, we obtain:

Where in the last inequality, we have applied Lemma 17 to the sequences $\rho_{i}$ and $\xi_{i}$ defined by:

Applying the upper bound (14) to the final term of (13), we obtain:

where we have used the fact that $\operatorname{cost}_{{\cal{D}},d}(O)\leq\operatorname{cost}_{{\cal{D}},d}(A)$. Rearranging, we have

Appendix C Proof of Theorem 7

We first show that for every solution of the $k$-means problem on $X$ there is a corresponding solution of $k$-means problem on $X^{\prime}$ in which all centers lie in ${\cal{C}}$, and vice versa.

For every partition $S=\left\langle S_{1},\ldots,S_{k}\right\rangle$ of $X$, there is a corresponding clustering of $X^{\prime}$ given by $S^{\prime}=\left\langle\varphi(S_{1}),\ldots,\varphi(S_{k})\right\rangle$ and some centers $C^{\prime}=\left\langle c_{1}^{\prime},\ldots,c_{k}^{\prime}\right\rangle\subseteq{\cal{C}}$ such that:

Part 1: Consider a partition $S=\left\langle S_{1},\ldots,S_{k}\right\rangle$ of $X$ and the corresponding partition $S^{\prime}=\left\langle S_{1}^{\prime},\dots,S_{k}^{\prime}\right\rangle$ of $X^{\prime}$, where $S_{i}^{\prime}=\varphi(S_{i})$. Let $c_{i}^{\prime}=\operatorname*{arg\,min}_{c\in{\cal{C}}}\sum_{x\in S_{i}^{\prime}}\|x^{\prime}-c\|^{2}$ for $i\in\left\{1,\dots,k\right\}$. Because ${\cal{C}}$ is an $\varepsilon^{\prime}$-approximate centroid set for $X^{\prime}$, we have, for each cluster $S_{i}^{\prime}$,

Part 2: Consider a partition $S^{\prime}=\left\langle S_{1}^{\prime},\ldots,S_{k}^{\prime}\right\rangle$ of $X^{\prime}$ and the corresponding partition $S=\left\langle S_{1},\ldots,S_{k}\right\rangle$ of $X$, where $S_{i}=\varphi^{-1}(S_{i})$. Define the centers $c_{i}=\sum_{x\in S_{i}}x/|S_{i}|$. Then, for each cluster $S_{i}$, we have:

Now we are ready to define instance $\langle{\cal{D}},{\cal{C}},d\rangle$. Let ${\cal{D}}=X^{\prime}$, ${\cal{C}}$ be the $\varepsilon$-approximate centroid we defined above, and $d(c,x)=\|c-x\|^{2}$ for every $c\in{\cal{C}}$ and $x\in{\cal{D}}$. Define $\psi:{\cal{D}}\to X$ by $\psi(x)=\varphi^{-1}(x)$.

We prove that our reduction, which maps instance $X$ of $k$-means to instance $\langle{\cal{D}},{\cal{C}},d\rangle$ of $k$-median, satisfies the conditions of the theorem.

Our reduction produces an instance that satisfies the following properties:

The distance function $d$ satisfies the 3-relaxed 3-hop triangle inequality on ${\cal{D}}\cup{\cal{C}}$.

For every partition $S=\left\langle S_{1},\ldots,S_{k}\right\rangle$ of ${\cal{D}}$ and the corresponding partition $\psi(S)=\left\langle\psi(S_{1}),\ldots,\psi(S_{k})\right\rangle$ of $X$, we have

For claim 2, consider any partition $S$ of ${\cal{D}}$. Let $T=\psi(S)$ be the corresponding partition of $X$, given by $T_{i}=\psi(S_{i})$. Then, from our definition of $d$, we have $\operatorname{cost}_{{\cal{D}},d}(S)=\operatorname{cost}_{X^{\prime}}(S)$. Moreover, by Lemma 18, we have $\operatorname{cost}_{X^{\prime}}(S)$ is between $\operatorname{cost}_{X}(T)$ and $(1+\varepsilon^{\prime})^{2}\operatorname{cost}_{X}(T)$. Thus,