Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics

Introduction

In this paper, we address three fundamental problems, facility location, $k$-median and $k$-means clustering, in two settings, graphs and Euclidean spaces. The problem of approximating $k$-means clustering in low-dimensional Euclidean space has been studied since at least 1994 ; since then, many researchers have given approximation schemes that are polynomial for fixed $k$ but exponential in $k$. Very recently, building on , a bicriteria polynomial-time approximation scheme has been given for $k$-means: it finds $(1+\epsilon)k$ centers whose cost is at most $1+\epsilon$ times the cost of an optimal $k$-means solution. As the authors of that paper point out, it remained an open question whether there is a true polynomial-time approximation scheme for $k$-means in the plane (where $k$ is considered part of the input); the best polynomial-time approximation bound known was $9+\epsilon$. In this paper, we resolve this open question by giving the first polynomial-time approximation scheme for arbitrary (i.e. nonconstant) $k$ in low-dimensional Euclidean space.

Our analysis of the $k$-means approximation scheme shows that it can also be applied to graphs belonging to a fixed nontrivial minor-closed family.Contracting an edge of a graph means identifying its endpoints and then removing it. A graph $H$ is a minor of graph $G$ if $H$ can be obtained from $H$ by edge deletions and edge contractions. The family of planar graphs, for example, is closed under taking minors, as is the family of graphs embeddable on a surface of genus $g$, for any fixed integer $g>0$. We say a minor-closed family is nontrivial if it omits at least one graph.

For example, for any fixed integer $g$, graphs embeddable on a surface of genus $g$ form such a family. In particular, planar graphs forms such a family. Thus we also obtain the first polynomial-time approximation scheme for $k$-means in planar graphs.

The problems of (uncapacitated) metric facility location and $k$-median in graphs has similarly been studied for many years. The first polynomial-time approximation algorithm, with a logarithmic performance guarantee, was given by Hochbaum in 1982 . The first polynomial-time approximation algorithm to achieve a constant approximation ratio was given by Shmoys et al. in 1997. It was later improved by Jain and Vazirani and by Arya et al. . The current best approximation algorithm for metric (uncapacitated) facility location, due to Li, has approximation ratio 1.488 . Guha and Khuller proved that there exists no polynomial-time approximation algorithm with approximation ratio of 1.463 for metric facility location problem unless $NP\subseteq DTIME[n^{O(\log\log n)}]$. The current best approximation ratio for the $k$-median problem is $1+\sqrt{3}$ by Li and Svensson .

In order to obtain a substantially better approximation ratio, therefore, one must restrict attention to special metrics. Because facility location problems often arise on the surface of the earth, it is natural to consider the metrics induced by planar graphs. Researchers have been trying to find a polynomial-time approximation scheme for the planar restriction for many years. An unpublished manuscript by Ageev dating back at least to 2001 addressed the planar case via a straightforward application of Baker’s method , giving an algorithm whose performance on an instance depends on how much of the cost of the optimal solution is facility-opening cost. Despite the title of the manuscript, the algorithm is not an approximation scheme for instances with arbitrary weights. Since then there have been no results on the problem despite efforts by several researchers in the area.

In this paper, we give the first polynomial-time approximation scheme for (uncapacitated uniform) facility location and $k$-median where the metric is that induced by a planar graph or, more generally a graph belonging to a fixed nontrivial minor-closed family.

We describe a simple and natural, and previously studied local-search algorithm for clustering problems, parameterized by the desired cluster size $k$, the objective function $\text{cost}(\cdot)$, and a parameter $s$ governing the local-search neighborhood.

For any fixed integers $p,d>0$, there is a constant $c$ such that, for any $0<\varepsilon<1/2$, applying Algorithm 1 to the $d$-dimensional Euclidean space with cost function

and $s=1/\varepsilon^{c}$ yields a solution $S$ whose cost is at most $1+\varepsilon$ times the minimum.

When $p=2$, the objective function is the $k$-means objective function. When $p=1$, the objective function is that of $k$-median.

For any integer $d>0$, there is a polynomial-time approximation scheme for the $k$-means problem in $d$-dimensional Euclidean spaces.

Algorithm 1 can also be applied to the metric completion of a graph.

Let $\mathcal{K}$ be a nontrivial minor-closed family of edge-weighted graphs. For any fixed integer $p>0$, there is a constant $c$ with the following property. For any $0<\varepsilon<1/2$, for any $G\in\mathcal{K}$, Algorithm 1 applied to the metric completion of $G$ with cost function

and with $s=1/\varepsilon^{c}$ yields a solution $S$ whose cost is at most $1+\varepsilon$ times the minimum.

It is straightforward to implement Algorithm 1 applied to the metric completion of a graph. As before, the number of iterations is $O(n/\varepsilon)$ where $n$ is the number of clients. We therefore obtain:

There is a polynomial-time approximation scheme for $k$-means and for $k$-median in planar graphs and in bounded-genus graphs.

More generally, for any nontrivial minor-closed family of edge-weighted graphs, there is a polynomial-time approximation schemes for $k$-means and for $k$-median for graphs in that family.

The local-search algorithm is easily adapted to the case where we do not specify the number of clusters but instead specify a per-cluster cost. This case includes a variant of the facility location problem.

The Uncapacitated Uniform Facility Location problem is as follows: given a finite metric space, a subset $C$ of points, and a facility opening cost $f$, find a subset $S$ of points that minimizes $\text{cost}(S)=f|S|+\sum_{c\in C}\min_{u\in S}\text{dist}(c,u)$.

To address this problem, we use a simple modification of the local-search algorithm given earlier.

Fix a nontrivial minor-closed family $\mathcal{K}$ of graphs. There is a constant $c$ such that, when Algorithm 2 is applied to the metric completion of a graph in $\mathcal{K}$ with

and $s=1/\varepsilon^{c}$, the output has cost at most $1+\varepsilon$ times the minimum.

In fact, for $p=1$, setting $s=c/\varepsilon^{2}$ suffices to achieve a $1+\varepsilon$ approximation. The theorem implies the following:

Fix a nontrivial minor-closed family $\mathcal{K}$ of edge-weighted graphs. There is a polynomial-time approximation scheme for uniform uncapacitated facility location in graphs of $\mathcal{K}$.

2 Related work

In arbitrary metric spaces, it is NP-hard to approximate the $k$-median and $k$-means problems within a factor of $1+2/e$ and $1+3/e$ respectively, see Guha and Khuller and Jain et al. . In the case of Euclidean space, Guruswami and Indyk showed that there is no PTAS for $k$-median if both $k$ and $d$ are part of the input. More recently, Awasthi et al. showed APX-Hardness for $k$-means if both $k$ and $d$ are part of the input.

In Euclidean spaces, $(1+\varepsilon)$-approximation algorithms for $k$-median have been proposed when $k$ or $d$ is fixed. For example, when $k$ is fixed, there exists different PTAS (See and for the best known so far). When $d$ is fixed, Arora et al. gave the first PTAS for the $k$-median problem. This result was subsequently improved to an efficient PTAS by Kolliopoulos et al. and Har-Peled et al. .

For the $k$-means problem, Kanungo et al. showed that local search achieves a $9+\varepsilon$-approximation in general metrics and this remains the best known approximation guarantee so far even for fixed $d$. There are also a variety of results for $k$-means and $k$-median when the input has some stability conditions (see for example ) or in the context of smoothed analysis (see for example ).

Local Search for metric $k$-median was first analyzed by Korupolu et al . They gave a bicriteria approximation using $k\cdot(1+\varepsilon)$ centers an achieving a cost of at most $3+5/\varepsilon$ times the cost of the optimum $k$-clustering. This was later improved to $k\cdot(1+\varepsilon)$ centers an achieving a cost of at most $2+2/\varepsilon$ times the cost of the optimum $k$-clustering by Charikar an Guha . Arya et al. gave the first analysis showing that Local Search with a neighborhood of size $1/\varepsilon$ gives a $3+2\varepsilon$ approximation to $k$-median. Moreover, they show that this bound is tight. As mentioned earlier, Kanungo et al. showed that local search is a $9+\varepsilon$-approximation for $k$-means in general metrics. Local search is a very popular algorithm for clustering and has been widely used : see in the context of parallel algorithms, in the streaming model and for distributed computing. See for a general introduction to theory and practice of local search.

After we had written up our results and while we were editing the submission, we noticed a recent ArXiv paper that has similar results for doubling metrics.

Techniques

One key ingredient in our analyses is the existence of a certain kind of decomposition of the input called a weak $r$-division. The concept (in a stronger form) is due to Frederickson in the context of planar graphs. It is straightforward to extend it to any family of graphs with balanced separators of size sublinear-polynomial. We also define a weak $r$-division for points in a Euclidean space, and show that such a decomposition always exists. These definitions and results are in Sections 3.1 and 3.2. Note that $r$-divisions play no role in our algorithm; only the analysis uses them.

Chan and Har-Peled showed that local search can be used to obtain a PTAS for (unweighted) maximum independent pseudo-disks in the plane, which implies the analogous result for planar graphs. More generally, Har-Peled and Quanrud show that local search can be used to obtain PTASs for several problems including independent set, set cover, and dominating set, in graphs with polynomial expansion. These graphs have small separators and therefore $r$-divisions. However, our analysis of local search for clustering requires not only that the input graph have an $r$-division but that a minor of the input graph have an $r$-division. This is not true of graphs of polynomial expansion. Indeed, we show in Section 2.3 that there are low-density graphs in low-dimensional space (which are therefore polynomial-expansion graphs) for which our local-search algorithm produces a solution that is worse than the optimum by at least a constant factor.

Thus one of our technical contributions is showing how to take advantage of a property possessed by nontrivial minor-closed graph families that is not possessed by polynomial-expansion graph families.

2 Isolation

In order to obtain our approximation schemes for $k$-means and $k$-median clustering, we need another technique. As mentioned earlier, a bicriteria approximation scheme for $k$-means was already known; the solution it returns has more than $k$ centers. It seems hard to avoid an increase in the number of centers in comparing a locally optimal solution to a globally optimal solution. It would help if we could show that the globally optimal solution could be modified so as to reduce the number of centers below $k$ while only slightly increasing the cost; we could then compare the local solution to this modified global solution, and the increase in the number of centers would leave the number no more than $k$.

We now give the formal definition of 1-1 isolated.

Let $\varepsilon<1/2$ be a positive constant and $\mathcal{L}$ and $\mathcal{G}$ be two solutions for the $k$-clustering problem with exponent $p$. Let $\bar{k}$ denote the number of facilities $f$ of $\mathcal{G}$ that are not in a 1-1 isolated region. There exists a set $S_{0}$ of facilities of $\mathcal{G}$ of size at least $\varepsilon^{3}\bar{k}/6$ that can be removed from $\mathcal{G}$ at low cost: $\text{cost}(\mathcal{G}-S_{0})\leq(1+2^{3p+1}\varepsilon)\text{cost}(\mathcal{G})+2^{3p+1}\varepsilon\text{cost}(\mathcal{L})$.

Note that the following theorem does not assume that $\mathcal{L}$ is a local optimum and $\mathcal{G}$ is an optimal solution. Thus we believe that this theorem can be of broader interest. We now define the concept of isolated regions; 1-1-isolated regions correspond to the special case of isolated regions when $\mathcal{L}_{0}$ consists of a single facility.

Given a facility $f_{0}\in\mathcal{G}$ and a set of facilities $\mathcal{L}_{0}\subseteq\mathcal{L}$, we say that the pair $(f_{0},\mathcal{L}_{0})$ is an isolated region if

For each facility $f^{\prime}\in\mathcal{L}_{0}$, most of the clients served by $f^{\prime}$ in $\mathcal{L}$ are served by $f_{0}$ in $\mathcal{G}$: in other words, $|V_{\mathcal{L}}(f^{\prime})\cap V_{\mathcal{G}}(f_{0})|\geq(1-\varepsilon)|V_{\mathcal{L}}(f^{\prime})|$, and

Most of the clients served by $f_{0}$ in $\mathcal{G}$ are served by facilities of $\mathcal{L}_{0}$ in $\mathcal{L}$: in other words, $|V_{\mathcal{L}}(\mathcal{L}_{0})\cap V_{\mathcal{G}}(f_{0})|\geq(1-\varepsilon)|V_{\mathcal{G}}(f_{0})|$;

Finally, if $(f_{0},\mathcal{L}_{0})$ is an isolated region, we say that $f_{0}$ and the elements of $\mathcal{L}_{0}$ are isolated.

3 Tightness of the results

For any $w,t$, there exists an infinite family of graphs excluding $K_{w}$ as a $t$-shallow minor such that for any constant $\varepsilon$, local search with neighborhoods of size $1/\varepsilon$ might return a solution of cost at least $3\text{OPT}$.

See Figure 1 and for a complete proof that local search performs badly on the instance depicted in the figure.

For any $\rho$, there exists an infinite family of graphs that are low-density graphs such that for any constant $\varepsilon$, local search with neighborhoods of size $1/\varepsilon$ might return a solution of cost at least $3\text{OPT}$.

The proposition follows from encoding the graph of Figure 1 as an low-density graph.

We additionally remark that Awasthi et al. show that the $k$-means problem is APX-Hard for any non-constant dimension $d$. Moreover, Kanungo et al. give an example where local search returns a solution of cost at least $9\text{OPT}$.

Preliminaries

We will use the following technical lemma in order to give a general proof that encompasses both the cases of $k$-median and $k$-means. Throughout the paper we assume $p$ constant and define $\varepsilon_{1}$ to be a positive constant.

Let $p\geq 0$ and $0<\varepsilon_{1}<1/2$. For any $a,b,c\in A\cup F$, we have

Moreover, by the binomial theorem, $\text{dist}(a,b)^{p}=(\text{dist}(a,c)+\text{dist}(c,b))^{p}\leq 2^{p}(\text{cost}(a,c)^{p}+\text{cost}(c,b)^{p}).$ ∎

For a graph $G$, we use $V(G)$ and $E(G)$ to denote the set of vertices of $G$ and the set of edges of $G$, respectively. For a subgraph $H$ of $G$, the vertex boundary of $H$ in $G$, denoted $\partial_{G}(H)$, is the set of vertices $v$ such that $v$ is in $H$ but has an incident edge that is not in $H$. (We might write $\partial(H)$ if $G$ is unambiguous.) A vertex in the vertex boundary of $H$ is called a boundary vertex of $H$. A vertex of $H$ that is not a boundary vertex of $H$ is called an internal vertex. We denote the set of internal vertices of $H$ as $\mathcal{I}(H)$.

Let $c_{1}$ and $c_{2}$ be constants (depending on $\mathcal{G}$). For a number $r$, a weak $r$-division of a graph $G$ (with respect to $c_{1},c_{2}$) is a collection $\mathcal{R}$ of subgraphs of $G$, called regions, with the following properties.

Each edge of $G$ is in exactly one region.

The number of regions is at most $c_{1}|V(G)|/r$.

Each region contains at most $r$ vertices.

The number of boundary vertices, summed over all regions, is at most $c_{2}|V(G)|/r^{1/2}$.

A family of graphs $F$ is said to be closed under taking minor (minor-closed) if for any graph $G\in F$, for any minor $H$ of $G$, we have $H\in F$.

Let $\mathcal{K}$ be a nontrivial minor-closed family of graphs. There exist $c_{1},c_{2}$ such that every graph in $\mathcal{K}$ has a weak $r$-division with respect to $c_{1},c_{2}$.

Alon, Seymour, and Thomas proved a separator theorem for the family of graphs excluding a fixed graph as a minor. Any nontrivial minor-closed family excludes some graph as a minor (else it is trivial). Frederickson gave a construction for a stronger kind of $r$-division of a planar graph. The construction uses nothing of planar graphs except that they have such separators. ∎

Let $G$ be an undirected graph with edge-lengths. Fix an arbitrary priority ordering of the vertex set $V(G)$. For every subset $S$ of $V(G)$, we define the Voronoi partition with respect to $S$. For each vertex $v\in S$, the Voronoi cell with center $v$, denoted $V_{S}(v)$, is the set of vertices that are closer to $v$ than to any other vertex in $S$, breaking ties in favor of the highest-priority vertex of $S$.

For any $S$, for any vertex $v\in S$, the induced subgraph $G[V_{S}(v)]$ is a connected subgraph of $G$.

Let $u\in V_{S}(v)$, and let $p$ denote a $v$-to-$u$ shortest path. Let $w$ be a vertex on $P$. Assume for a contradiction that, for some vertex $v^{\prime}\in S$, either the $v^{\prime}$-to-$w$ shortest path $p^{\prime}$ is shorter than the shortest $v$-to-$w$ path, or it is no longer and $v^{\prime}$ has higher priority than $v$. Replacing the $v$-to-$w$ subpath of $p$ with $p^{\prime}$ yields a $v$-to-$u$ path that either is shorter than $p$ or is no longer than $p$ and originates at a higher-priority vertex than $v$. ∎

It follows that, for any vertex $v$ of $G$, contracting the edges of the subgraph $G[V_{S}(v)]$ yields a single vertex.

We define $G_{\text{Vor}(S)}$ as the graph obtained from $G$ by contracting every edge of $G[V_{S}(v)]$ for every vertex $v\in S$. For each vertex $v\in S$, we denote by $\hat{v}$ the vertex of $G_{\text{Vor}(S)}$ resulting from contracting every edge of $G[V_{S}(v)]$.

If $G$ belongs to a minor-closed family $\mathcal{K}$ then so does $G_{\text{Vor}(S)}$.

2 Euclidean space r𝑟r-division

The number of regions is at most $c_{1}|C|/r$.

Each region contains at most $r$ points of $C\cup Z$.

$\sum_{R\in\mathcal{R}}|R\cap Z|\leq c_{2}|C|/r^{1/d}$.

Moreover, for any region $R_{i}$, $R_{i}\cap Z$ is a Voronoi separator for $R_{i}-Z$ and $(C\cup Z)-R_{i}$.

The following theorem is from [17, Theorem 3.7].

There are most $\sigma n$ points of $P$ in the sphere $S$ and at most $\sigma n$ points of $P$ not in $S$, and

$Z$ is a Voronoi separator of the points of $P$ inside $S$ from the points of $P$ outside $S$.

Here $c$ and $\sigma<1$ are constants that depends only on the dimension $d$.

From that theorem we can easily derive the following (see Section 8.1 for the proof):

3 Properties of the r𝑟r-Divisions

We present the properties of the $r$-divisions that we will be using for the analysis of the solution output by the local search algorithm.

Let $G=(V,E)$ be a graph excluding a fixed minor $H$ and $\mathcal{F}\subseteq V$. Let $H_{i}$ be a region of the $r$-division of $G_{\text{Vor}(\mathcal{F})}$. Suppose $c$ and $v$ are vertices of $G$ such that one of the vertices in $\{\hat{c},\hat{v}\}$ is a vertex of $H_{i}$ and the other is not an internal vertex of $H_{i}$. Then there exists a vertex $x\in\mathcal{F}$ such that $\hat{x}$ is a boundary vertex of the region $H_{i}$ and $\text{dist}(c,x)\leq\text{dist}(c,v)$.

Let $p$ be a shortest $c$-to-$v$ path in $G$. By the conditions on $\hat{c}$ and $\hat{v}$, there is some vertex $w$ of $p$ such that $\hat{w}$ is a boundary vertex of $H_{i}$. Let $x$ be the center of the Voronoi cell whose contraction yields $\hat{w}$. By definition of Voronoi cell, $\text{dist}(w,x)\leq\text{dist}(w,v)$. Therefore replacing the $w$-to-$v$ subpath of $p$ with the shortest $w$-to-$x$ path yields a path no longer than $p$. ∎

We obtain the analogous lemma for the Euclidean case, whose proof follows directly from the definition of $r$-division (i.e.: the fact that $Z$ is a Voronoi separator).

Facility Location in minor-closed graphs: Proof of Theorem 1.3

As a warm-up, we analyze Local Search for Uniform Facility Location (Algorithm 2) applied to the metric completion of an edge-weighted graph $G$ belonging to a nontrivial minor-closed family $\mathcal{K}$. The proof of the $k$-median and $k$-means results (for both Euclidean and minor-closed metrics), involve the use of Theorem 2.2 and a more complex analysis.

Throughout this section we consider a solution $\mathcal{L}$ output by Algorithm 2 (the “local” solution) and a globally optimal solution $\mathcal{G}$ of value OPT. Let $\mathcal{F}=\mathcal{L}\cup\mathcal{G}$. Let $r=1/\varepsilon^{2}$. Consider the graph $G_{\text{Vor}(\mathcal{F})}$ defined in Definition 3.4, and recall that each vertex of $G$ maps to a vertex $\hat{v}$ in the contracted graph $G_{\text{Vor}(\mathcal{F})}$.

Since $G$ belongs to $\mathcal{K}$ and $G_{\text{Vor}(\mathcal{F})}$ is obtained from $G$ by contraction, it too belongs to $\mathcal{K}$ and hence it has an $r$-division. Let $H_{1},\ldots H_{\kappa}$ be the regions of this $r$-division. For $i=1,\ldots,\kappa$, define $V_{i}$ and $B_{i}$ as follows:

That is, $V_{i}$ is the set of vertices in the union of the local solution and the global solution that map via contraction to vertices of the region $H_{i}$, and $B_{i}$ is the set of vertices in the union that map to boundary vertices of $H_{i}$.

Let $\mathcal{G}^{\prime}=\mathcal{G}\cup\bigcup_{i=1}^{\kappa}B_{i}$.

Fix a region $H_{i}$ of the $r$-division of $G_{\text{Vor}(\mathcal{F})}$. We define $\mathcal{L}_{i}=\mathcal{L}\cap V_{i}$ and $\mathcal{G}^{\prime}_{i}=\mathcal{G}^{\prime}\cap V_{i}$. We consider the mixed solution $\mathcal{M}^{i}$ defined as follows:

$|\mathcal{M}^{i}-\mathcal{L}|+|\mathcal{L}-\mathcal{M}^{i}|\leq 1/\varepsilon^{2}$.

To obtain $\mathcal{M}^{i}$ from $\mathcal{L}$, one can remove the vertices in $\mathcal{L}\cap V_{i}$ that are not in $\cal G^{\prime}$, and add the vertices in ${\cal G^{\prime}}\cap V_{i}$ that are not in $\mathcal{L}$. Thus the size of the symmetric difference is at most $|(\mathcal{L}\cup\mathcal{G}^{\prime})\cap V_{i}|$. Since the vertices of $\mathcal{L}\cup\mathcal{G}^{\prime}$ are centers of Voronoi cells, these vertices all map to different vertices in the contracted graph $G_{\text{Vor}(\mathcal{F})}$. Therefore $|(\mathcal{L}\cup\mathcal{G}^{\prime})\cap V_{i}|$ is at most the number of vertices in region $H_{i}$, which is at most $r=1/\varepsilon^{2}$. ∎

Let $c$ be a vertex of $G$ and $H_{i}$ a region. Then:

First suppose $\hat{c}$ is an internal vertex of $H_{i}$, and let $v$ be the facility in $\mathcal{M}^{i}$ closest to $c$. If $v$ is in $V_{i}$ then it is in $\mathcal{G}_{i}$, so $m_{c}^{i}=g^{\prime}_{i}$. Suppose $v$ is not in $V_{i}$. Then by Lemma 3.8 there is a vertex $x\in\mathcal{F}$ such that $\hat{x}$ is a boundary vertex of $H_{i}$ and $\text{dist}(c,x)\leq\text{dist}(c,v)$. As before, $x$ is in $\mathcal{G}^{\prime}_{i}$ so $m_{c}^{i}\leq g^{\prime}_{c}$. Since $g^{\prime}_{c}\leq g_{c}$, this proves the claimed upper bound.

Let $v$ be a vertex of $\mathcal{G}^{\prime}$. For $i=1,\ldots,\kappa$, if $\hat{v}$ is an internal vertex of the region $H_{i}$ then $v$ contributes only one towards the left-hand side. If $\hat{v}$ is a boundary vertex of $H_{i}$ then $v\in B_{i}$. Therefore

To finish the proof, we bound the sum in the right-hand side. Each vertex in $\mathcal{F}$ is the center of one Voronoi cell, so $G_{\text{Vor}(\mathcal{F})}$ has $|\mathcal{F}|$ vertices. For each region $H_{i}$, there is one vertex in $B_{i}$ that corresponds to each boundary vertex of $H_{i}$, so $\sum_{i=1}^{\kappa}|B_{i}|$ is the sum over all regions of the number of boundary vertices of that region, which, by Property 4 of $r$-divisions, is at most $c_{2}|\mathcal{F}|/r^{1/2}$, which, by choice of $r$, is at most $c_{2}\varepsilon|{\cal F}|$, which in turn is at most $c_{2}\varepsilon(|{\cal G}|+|\mathcal{L}|)$.

(Proof of Theorem 1.3) Lemma 4.1 and the stopping condition of Algorithm 2 imply the following:

Using Lemma 4.2 and summing over $c$ shows that

Combining Inequalities (1), (2) and (3), we obtain

We next sum this inequality over all $\kappa$ regions of the weak $r$-division and use Lemma 4.3.

Since $\kappa\leq c_{1}|\mathcal{F}|/r\leq c_{1}\varepsilon^{2}n$, we obtain

This completes the proof of Theorem 1.3. ∎

Clusters in minor-closed graphs: Proof of Theorem 1.2

We prove Theorem 1.2. The proof is similar for graphs and for points lying in $R^{d}$. It builds on the notions of isolation and 1-1 isolation introduced in Section 2.2.

We consider a solution $\mathcal{L}$ output by Algorithm 1 and an optimal solution $\mathcal{G}$. Let $\bar{\mathcal{F}}$ be the set of facilities of $\mathcal{L}$ and $\mathcal{G}$ that are not in a 1-1 isolated region and let $\bar{k}=|\bar{\mathcal{F}}|$.

Let $\mathcal{F}=\mathcal{G}_{1}\cup\mathcal{L}$. Let $R_{1},R_{2},\ldots$ be an $r$-division of $G^{\prime}_{\text{Vor}(\mathcal{F})}$ where $r=1/\varepsilon^{7}$. Define \mathcal{G}^{*}=\mathcal{G}_{1}\cup\{\text{boundary vertices of ther-division}\}.

The vertex sets of regions are of course not disjoint—a boundary vertex is in multiple regions—but it is convenient to represent them by disjoint sets. We therefore define a ground set $\Omega=\{(v,R)\ :v\text{ a vertex of }G^{\prime}_{\text{Vor}(\mathcal{F})},R\text{ a region containing }v\}$, and, for each region $R$, we define $\widehat{R}=\{(v,R)\ :\ v\text{ a vertex of }R\}$. Now $\widehat{R_{1}},\widehat{R_{2}},\ldots$ form a partition of $\Omega$. To allow us to go from an element of $\Omega$ back to a vertex, if $x=(v,R)$ we define $\widecheck{x}=v$. Finally, define $\widehat{\mathcal{G}}=\{(v,R)\in\Omega:\ v\in\mathcal{G}^{*}\}$.

Let $\bar{\mathcal{F}}$ be the set of facilities of $local$ and $\mathcal{G}$ that are not in 1-1 isolated regions.

$|\widehat{\mathcal{G}}|\leq|\mathcal{G}_{1}|+c_{2}\varepsilon^{3.5}|\bar{\mathcal{F}}|$, where $c_{2}$ is the constant in the definition of $r$-division.

Consider the $r$-division. Each 1-1 isolated region results in a connected component of size 2 in $G^{\prime}_{\text{Vor}(\mathcal{F})}$ and so no boundary vertices arise from such connected components. By the definition of $r$-division, the sum over regions of boundary vertices is at most $c_{2}\cdot|\bar{n}_{0}|/r^{1/2}$, where $\bar{n}_{0}$ is the total number of elements of $\mathcal{G}_{1}$ and $\mathcal{L}$ that are not in 1-1 isolated regions. Since $r=1/\varepsilon^{7}$, we have that $|\widehat{\mathcal{G}}|\leq|\mathcal{G}_{1}|+c_{2}\cdot\varepsilon^{4}|\bar{\mathcal{F}}|$. ∎

By Theorem 2.2, we have that $|\mathcal{G}_{1}|\leq k-\varepsilon^{3}\bar{k}/12$. By Lemma 5.1 we thus have

Let $\mathcal{S}=\{S_{1},...,S_{p}\}$ and $\{A,B\}$ be partitions of some ground set. Suppose $|A|\geq|B|$ and, for $=1,\ldots,p$, $1/(2\varepsilon^{2})\leq|S_{i}|\leq 1/\varepsilon^{2}$.

There exists a partition that is a coarsening of $\mathcal{S}$ satisfying the two following properties. For any part $C$ of the coarser partition,

Small Cardinality: $C$ is the union of $\mathcal{O}(1/\varepsilon^{5})$ parts of $\mathcal{S}$.

We now apply Lemma 5.3 to the partition $\widehat{R_{1}},\widehat{R_{2}},\ldots$ with $A=\{(v,R)\in\Omega\ :\ v\in\mathcal{L}\}$ and $B=\widehat{\mathcal{G}}$. We refer to the parts of the resulting coarse partition as super-regions. Each super-region $\mathcal{R}$ naturally corresponds to a subgraph of $G^{\prime}_{\text{Vor}(\mathcal{F})}$, the subgraph induced by $\{v\ :\ (v,R)\in\mathcal{R}\}$, and we sometimes use $\mathcal{R}$ to refer to this subgraph.

$|\mathcal{M}_{\mathcal{R}}-\mathcal{L}|+|\mathcal{L}-\mathcal{M}_{\mathcal{R}}|=O(1/\varepsilon^{12})$ and $|\mathcal{M}_{\mathcal{R}}|\leq k$.

Each region of the $r$-division contains at most $c_{1}/\varepsilon^{7}$ facilities where $c_{1}$ is the constant in the definition of $r$-divisions. By Lemma 5.3, each super-region is the union of $\mathcal{O}(1/\varepsilon^{5})$ regions ∎

We now define $g_{c}$ to be the cost of client $c$ in solution $\mathcal{G}^{*}$ and $l_{c}$ to be the cost of client $c$ in solution $\mathcal{L}$. For any client $c\in V_{\mathcal{G}}(f_{0})-V_{\mathcal{L}}(\mathcal{L}_{0})$ for some isolated region $(f_{0},\mathcal{L}_{0})$, define $\text{Reassign}_{\mathcal{G}^{*}\mapsto\mathcal{L}}(c)$ as the cost of assigning $c$ to the facility of $\mathcal{L}_{0}$ that is the closest to $f_{0}$. We let $\varepsilon_{1}$ be a positive constant that will be chosen later.

Consider an isolated region $(f_{0},\mathcal{L}_{0})$.

Substituting, we have that $\sum\limits_{c\in V_{\mathcal{G}}(f_{0})-V_{\mathcal{L}}(\mathcal{L}_{0})}\text{Reassign}_{\mathcal{L}\mapsto\mathcal{G}^{*}}(c)$ is at most

Similarly, for any client $c\in V_{\mathcal{L}}(\mathcal{L}_{0})-V_{\mathcal{G}}(f_{0})$ for some isolated region $(f_{0},\mathcal{L}_{0})$, define $\text{Reassign}_{\mathcal{L}\mapsto\mathcal{G}^{*}}$ as the cost of assigning $c$ to $f_{0}$.

Consider an isolated region $(f_{0},\mathcal{L}_{0})$.

For a client $c$ and a super-region $\mathcal{R}$, we define $m_{\mathcal{R}}(c)$ to be the cost of $c$ in the mixed solution $\mathcal{M}_{\mathcal{R}}$. Moreover, for each client $c$, we consider the facilities $v$ and $w$ that serve this client in solution $\mathcal{L}$ and $\mathcal{G}^{*}$ respectively. We define $l(c)$ to be an arbitrary pair $(v,R)\in\Omega$ and $g^{*}(c)$ to be an arbitrary pair $(w,R)\in\Omega$. We slightly abuse notation and say that $(v,R)$ is isolated if $v$ belongs to one of the isolated regions.

Let $c$ be a good client and $\mathcal{R}$ a super-region. The value of $m_{\mathcal{R}}(c)-l_{c}$ is less than or equal to:

Observe that if $g^{*}(c)\in\mathcal{R}$, then $m_{\mathcal{R}}(c)\leq g_{c}$ and the first case holds. Now, for any super-region $\mathcal{R}\not\ni l(c),g^{*}(c)$, $\mathcal{M}_{\mathcal{R}}$ contains the facility serving client $c$ in local. Thus its cost is at most $l_{c}$ and the second case holds. Finally, assume that $\mathcal{R}$ contains $l(c)$ and does not contain $g^{*}(c)$. If $\hat{c}$ belongs to $\mathcal{R}$, then by the separation property of the $r$-division (see Lemmas 3.8, 3.9), $g^{*}(c)\in\mathcal{R}$ and $m_{\mathcal{R}}(c)\leq g_{c}$. Otherwise, $\hat{c}\notin\mathcal{R}$, and so, by the separation property there must be a boundary vertex of $\mathcal{R}$ that is closer to $c$ than the facility that serves it in $\mathcal{L}$. Therefore, we have $m_{\mathcal{R}}(c)\leq l_{c}$ and the second case holds. ∎

Let $c$ be a bad client and $\mathcal{R}$ a super-region. The value of $m_{\mathcal{R}}(c)-l_{c}$ is less than or equal to:

By Lemma 5.4, for any super-region $\mathcal{R}$ the solution $\mathcal{M}_{\mathcal{R}}$ is in the local neighborhood of $\mathcal{L}$. By local optimality, we have

Observe that the number of regions is at most $k\leq n$. Thus, summing over all regions we have

Inverting summations and applying Corollary 4, we obtain

By definition of $\Lambda_{1}$ and since each client in $\Lambda_{1}$ is bad, applying Lemma 5.6 yields

Hence, for $\varepsilon$ small enough with respect to $p$ and $\varepsilon_{1}$, we have

Now, by definition of $\Lambda_{2}$ and since each client in $\Lambda_{2}$ is bad, applying Lemma 5.5 gives

since $\Lambda_{1},\Lambda_{2},\Lambda_{3}$ is a partition of the clients. Therefore, assuming $\varepsilon$ is small enough with respect to $p$ and $\varepsilon_{1}$, there exists a constant $c_{1}$ such that

Now, observe that $\text{cost}(\mathcal{G}^{*})\leq\text{cost}(\mathcal{G}_{1})$ since $\mathcal{G}_{1}\subseteq\mathcal{G}^{*}$. By Theorem 2.2, $\text{cost}(\mathcal{G}_{1})\leq(1+c_{1}\varepsilon)\text{cost}(\mathcal{G})+c_{1}\varepsilon\text{cost}(\mathcal{L})$. Combining concludes the proof of Theorem 1.2 ∎

Clusters in Euclidean space : Proof of Theorem 1.1

The point sets of regions are not disjoint since points of $Z$ appear in various regions. Thus, we again define a ground set $\Omega=\{(v,R)\ :v\text{ a point of }\mathcal{F},~{}R\text{ a region containing }v\}$, and, for each region $R$, we define $\widehat{R}=\{(v,R)\ :\ v\text{ a point of }R\}$. Now $\widehat{R_{1}},\widehat{R_{2}},\ldots$ form a partition of $\Omega$. To allow us to go from an element of $\Omega$ back to a point, if $x=(v,R)$ we define $\widecheck{x}=v$. Finally, define $\widehat{\mathcal{G}}=\{(v,R)\in\Omega:\ v\in\mathcal{G}^{*}\}$.

We now branch with the rest of the proof of Theorem 1.2, starting from Lemma 5.1.

Reducing the number of clusters : Proof of Theorem 2.2

Let $\varepsilon<1/2$ be a positive constant and $\mathcal{L}$ and $\mathcal{G}$ be two solutions for the $k$-clustering problem with exponent $p$. Let $\bar{k}$ denote the number of facilities $f$ of $\mathcal{G}$ that are not in a 1-1 isolated region. There exists a set $S_{0}$ of facilities of $\mathcal{G}$ of size at least $\varepsilon^{3}\bar{k}/6$ that can be removed from $\mathcal{G}$ at low cost: $\text{cost}(\mathcal{G}-S_{0})\leq(1+2^{3p+1}\varepsilon)\text{cost}(\mathcal{G})+2^{3p+1}\varepsilon\text{cost}(\mathcal{L})$.

Since the arcs of $H$ are dichromatic, if $f\in S_{0}$ then $\phi(f)\notin S_{0}$. Consider the solution $\mathcal{G}-S_{0}$. Client that belong to $V_{\mathcal{G}}(f)$ for some $f\in S_{0}$ can be assigned in $\mathcal{G}-S_{0}$ to a facility that is no farther than $\phi(f)$. Therefore, the cost of the solution $\mathcal{G}-S_{0}$ is at most $\text{cost}(\mathcal{G})+2^{3p+1}\varepsilon\cdot(\text{cost}(\mathcal{L})+\text{cost}(\mathcal{G}))$.

We now define $g_{c}$ to be the cost of client $c$ in solution $\mathcal{G}^{*}$ and $l_{c}$ to be the cost of client $c$ in solution $\mathcal{L}$.

Putting $\Delta_{1},\Delta_{2},\Delta_{3},\Delta_{4}$ together we obtain that the total cost increase induced by the reassignment is at most $2^{3p+1}(\text{cost}(\mathcal{G})+\text{cost}(\mathcal{L}))/\varepsilon^{2}.$

Postponed proofs

We describe a recursive procedure to construct the set $Z$ in the definition of weak $r$-division of $C$. Assuming that $|C|>r$, find a sphere $S$ and a set $Z_{0}$ satisfying Theorem 3.6. Let $Z_{1}$ be the result of applying the procedure to the union of $Z_{0}$ with the set of points inside $C$, and similarly obtain $Z_{2}$ from the set of points outside $C$. Return $Z_{0}\cup Z_{1}\cup Z_{2}$.

It is clear that the set $Z$ together with its induced partition $\mathcal{R}$ of $C$ returned by the procedure satisfies all the properties of a weak $r$-division except for Property 4, which requires some calculation. Let $b(n)=\sum_{R\in\mathcal{R}}|R\cap Z|$ when the procedure is applied to a set $C$ of size at most $n$, where $n>(1-\sigma)r$. If $n\leq r$ then $b(n)=0$, and if $n>r$ then

We show by induction that $b(n)\leq\beta\frac{n}{r^{1/d}}-\gamma n^{1-1/d}$ for suitable constants $\beta,\gamma>0$ to be determined. We postpone the basis of the induction until $\beta,\gamma$ are selected.

The function $f(x)=x^{1-1/d}+(1-x)^{1-1/d}$ is strictly concave for $x\in$, as can be seen by taking its second derivative. For any $\alpha\in[1-\sigma,\sigma]$, there exists a number $0<\mu<1$ such that $\alpha=(1-\mu)(1-\sigma)+\mu\sigma$. By concavity, therefore, $f(\alpha)\geq(1-\mu)f(1-\sigma)+\mu f(\sigma)$. Since a weighted average is at least the minimum, $(1-\mu)f(1-\sigma)+\mu f(\sigma)\geq\min\{f(1-\sigma),f(\sigma)\}$. Write $f(1-\sigma)=f(\sigma)=1+\delta$. Since $f$ is strictly concave, $\delta>0$. We choose $\gamma=(c+2c/r^{1/d})/\delta$, for then the first term in Inequality 7 is bounded by $\gamma\delta n^{1-1/d}$, and we obtain $b(n)\leq\beta\frac{n}{r^{1/d}}-\gamma n^{1-1/d}$.

For the basis of the induction, suppose $n>(1-\sigma)r$. Then

which is nonnegative for an appropriate choice of $\beta$ depending on $\sigma$ and $\gamma$. ∎

References