Relax, no need to round: integrality of clustering formulations

Introduction

Convex relaxations have proved to be extremely useful in solving or approximately solving difficult optimization problems. In theoretical computer science, the “relax and round” paradigm is now standard: given an optimization problem over a difficult (non-convex) feasible set, first relax the feasible set to a larger (convex) region over which the optimization problem is convex, then round the resulting optimal solution back to a point in the feasible set. Such convex relaxations generally serve a dual purpose: (i) they can be solved efficiently, and thus their solution gives a good starting point for the rounding step , and (ii) the value of the optimal solution to the convex relaxation serves as a good bound on the true optimal solution, and this can be used to certify the performance of the overall algorithm. Often, the feasible set is non-convex due to integral constraints of the form $x_{i}\in\{0,1\}$, so that the relaxed convex set is given by the interval constraints $x_{i}\in$.

The study of convex relaxations in theoretical computer science has typically focused on how well such relaxations can approximate the objective function. This is captured by the approximation factor that can be obtained, i.e., how much worse in cost the integer rounded solution can be be in terms of the cost of the optimal fractional solution to the convex relaxation. However, in many practical scenarios, the choice of using a particular objective function is only a means to recovering the true hidden solution. For instance, when solving a clustering problem, the goal is to find an underlying ground truth clustering of the given data set. Modeling this problem via minimizing a particular objective function (such as $k$-median, $k$-means etc.) is a convenient mathematical choice, albeit the true goal still being to approximate the ground truth rather than the objective. In such scenarios, it is natural to ask if one can use convex relaxations directly to obtain the underlying ground truth solution and bypass the rounding step. In practice, optimal solutions of convex relaxations are often observed to also optimal for the original problem. As a result, one no longer needs the rounding step and the optimal solution can be recovered directly from solving the relaxed problem . We refer to this occurrence as exact recovery, tightness, or integrality, of the convex relaxation. Currently, there is very little theoretical understanding of this phenomenon (see e.g. ). Motivated by this question, our goal is to understand whether and when convex relaxations can in fact lead to exact recovery, i.e. yield the optimum solution for the underlying discrete optimization problem. This question also motivates the study and comparison of different relaxations for the same problem, in terms of their ability to produce integral optimum solutions. This is different from the typical goal of choosing the relaxation which yields algorithms with the best approximation factor. We believe that this is an interesting lens for examining convex relaxations that yields different insights into their strengths and weaknesses.

The phenomenon of exact recovery is understood in certain cases. A classical result says that network flow problems (e.g. maximum flow or minimum cost flow problems), or more generally any integer programming problem whose constraints are totally unimodular, all vertex solutions in the feasible set of the linear programming relaxation are integral, and hence the optimal solution (necessarily a vertex solution) is also integral . Integrality of convex relaxations have also been studied in LP decoding, where linear programming techniques are used to decode LDPC codes . More recently, in the statistical signal processing community, the seminal papers on compressive sensing set a precedent for proving “with high probability” tightness results: many optimization problems, while NP hard in the worst case, have tight convex relaxations with high probability over a distributions on input parameters. Subsequently, similar phenomena and guarantees have emerged in low-rank matrix completion problems , and in graph partition problems . Some other examples include multireference alignment and the study of MIMO channels . Among these works, the graph partitioning problems are most closely related to the clustering problems considered here; still, there are fundamental differences as discussed in Section 1.5. Convex relaxations have also been shown to recover optimal solutions to certain “stable” instances of graph partitioning problems such as Max-Cut and for inference in graphical models .

We will focus on integrality for convex relaxations of geometric clustering problems: given an initial set of data, map the data into a metric space, define an objective function over the points and solve for the optimal or an approximately optimal solution to the objective function. Then we can assume we are given a finite set of points $P=\{x_{1},\ldots,x_{n}\}$ in a metric space $(X,d)$ which we would like to partition into $k$ disjoint clusters. Two of the most commonly studied objective functions in the literature are $k$-median and $k$-means, depicted in Figure 1. In the $k$-median (also known as $k$-medoid) problem, clusters are specified by centers: $k$ representative points from within the set $P$ denoted by $c_{1},c_{2},\ldots,c_{k}$. The corresponding partitioning is obtained by assigning each point to its closest center. The cost incurred by a point is the distance to its assigned center, and the goal is to find $k$ center points that minimize the sum of the costs of the points in $P$:

The identity $\sum_{x_{i}\in A_{t}}d^{2}(x_{i},c_{t})=\frac{1}{2}\frac{1}{|A_{t}|}\sum_{x_{i},x_{j}\in A_{t}}d^{2}(x_{i},x_{j}),$ allows us to re-express the $k$-means problem as the following optimization problem:

2. Prior work

The $k$-median and the $k$-means problems and their LP relaxations have been extensively studied from an approximation point of view. Both problems can be expressed as integer programming problems – see (1) and (2) below – which are NP-hard to optimize . There exist, for both problems, approximation algorithms which achieve a constant factor approximation . The $k$-median objective is closely related to the well studied facility location problem and the best known algorithms use convex relaxations via a rounding step. For $k$-means there also exist very effective heuristics that although having provable guarantees in some cases , may, in general, converge to local minima of the objective function. SDP relaxations of the $k$-means optimization problem were previously introduced , albeit without exact recovery guarantees.

3. Our contribution

We study integrality for three different convex relaxations of the $k$-median and $k$-means objectives:

A standard linear programming (LP) relaxation of the $k$-median integer program,

A linear programming (LP) relaxation of the $k$-means integer program, and

A semidefinite programming (SDP) relaxation of the $k$-means integer program (closely related to a previously proposed SDP relaxation for $k$-means ),

Each of these relaxations produces integer solutions if the point set partitions into $k$ clusters and the intra-cluster separation distance (distance between cluster centers) is sufficiently large. As the separation distance decreases to 2 (at which point clusters begin to overlap and the “cluster solution” is no longer well-defined), a phase transition occurs for the $k$-means relaxations, and we begin to see fractional optimal solutions. We now present informal statements of our main results; see specific sections for more details.

Under the same setting as above and with high probability, a simple LP relaxation for the $k$-means objective fails to recover the exact clusters at separation $\Delta<4$, even for $k=2$ clusters.

Under the same setting as above and with high probability, an SDP relaxation for the $k$-means objective recovers the clusters up to separation $\Delta>2\sqrt{2}(1+\sqrt{1/m})$.

Theorems 1 and 2 are tight in their dependence on the cluster separation $\Delta$. Theorem 3 is not tight and we conjecture the result should hold for separation $\Delta>2+\epsilon$.

Under the same setting as in Theorem 1 the SDP relaxation for the $k$-means objective recovers the clusters at separation $\Delta>2+\epsilon$ with high probability.

Under the assumptions of the theorems above, popular heuristic algorithms such as Partitioning around Medoids (PAM) and Lloyd’s algorithm (for k-median and k-means, respectively) can fail with high probability. Even with arbitrarily large cluster separation, variants of Llody’s algorithm such as k-means++ with overseeding by any constant factor fails with high probability at exact cluster recovery. See Section 5 for details.

In section 4 we derive a deterministic geometric condition on a set of points for tightness of the $k$-means SDP called “average separation” (see Definitions 4 and 5), and Theorem 3 follows by proving that this condition holds with high probability for the random point model. We believe that a more refined set of deterministic conditions should exist which will lead to the proof of Conjecture 4.

As an addition to Theorem 1 we show that the popular Primal-Dual approximation algorithm for $k$-median also recovers the true clustering under the same assumptions. In fact, in this case, when executing the algorithm one does not need to run the second stage of choosing independent sets among the set of potential centers. See Appendix F for details.

The main mathematical ingredients to establish the results above consist in the use of concentration of measure results, both scalar and matrix versions, to build appropriate dual certificates for these problems. That is, we construct deterministic sufficient conditions for the convex relaxations to be integral, and then demonstrate that with high probability, such conditions are satisfied for the random input at sufficiently high cluster separation. At the same time, the complementary slackness conditions for the $k$-means LP reveal that exact recovery for the $k$-means LP is possible with high probability if and only if the cluster separation satisfies $\Delta\geq 4$.

4. Why Study Convex Relaxations?

At this point, we reiterate why we focus on exact recovery guarantees for convex relaxations in particular, as opposed to other popular algorithms, such as the $k$-means heuristic (a.k.a. Lloyd’s algorithm ). In fact, there has been substantial work on studying exact recovery conditions for such heuristics . However, one disadvantage of using these heuristics is that there is typically no way to guarantee that the heuristic is computing a good solution. In other words, even if such a heuristic is recovering an optimal solution to the underlying combinatorial optimization problem, we cannot ascertain such optimality just by looking at the output of the heuristic. Indeed, a crucial advantage of convex relaxations over other heuristics is that they come with a certificate that the produced solution is optimal, when this is the case. This property makes convex relaxations appealing over other iterative heuristics. There is also a large body of work on studying clustering problems under distributional or deterministic stability conditions . However, the algorithms designed are usually tailored to specific assumptions on the input. On the other hand, the convex relaxation algorithms we study are not tied to any particular data distribution, and only depend on $k$, the number of clusters.

Nevertheless, it is natural to ask how well the commonly-used heuristics for $k$-means and $k$-median perform on the instances we analyze. Toward this end, we show (see Section 5) that heuristics such as Lloyd’s algorithm and kmeans ++ (even with initialization procedures like overseeding) can fail to recover clusters with exponentially high probability, even when the cluster separation is arbitrarily high, far within the regime where Theorems 1 and 3 imply that the $k$-means and $k$-median convex relaxations are guaranteed (with high probability) to recover the clusters correctly.

5. Comparison with stochastic block models

The stochastic block model (SBM) with $k$ communities is a simple random graph model for graph with a community behavior. Each edge is random (similarly to an Erdős Rényi graph) where the edges are independent and the probability of each depends on wether it is a intra- or inter-community edge. The task consists of recovering the hidden communities, and is often known as community detection or graph partitioning; in the particular case of two communities this is also known as planted bisection. Recently, and have obtained sharp thresholds for which problem parameters it is, in the $k=2$ case, possible to correctly recover the labels of every point. Moreover an SDP relaxation is proposed in and shown to be integral and perform exact recovery close to the optimal threshold.

Although sharing many characteristics with our problem, the stochastic block model differs from the clustering problems we consider in many fundamental ways. Our objective is to cluster a point cloud in euclidean space. Although our results are for specific models, they are obtained from establishing conditions on the point clouds that could potentially be established for other, perhaps even deterministic, point clouds as the methods we analyze are not tied to the point model; they are clustering methods widely used in many settings. In contrast, the convex relaxation mentioned above for the SBM is based on the maximum likelihood estimator for the graph model. Moreover, while the SBM produces graphs whose edges are independent, our random model is on the vertices, which creates non-trivial dependencies in the edges (distances). Another technical difficulty in the clustering problems we study, that is not present in the SBM, is the inhomogeneity of the points; the points in the SBM are fairly uniform, even though there might be small variations, the inner and outer degree of every node will be comparable. On the other hand, in our setting, points close to other clusters have a very different distance profile from points near the center of their own cluster.

Integrality for the k𝑘k-median LP relaxation

The $k$-median problem, expressed in the form of an integer programming problem (1), has a natural linear programming relaxation given by relaxing the integral constraints to interval constraints. This linear program is given in (3); its dual linear program is given in (4).

For $A_{j}\subseteq P$, let $c_{j}$ the center of $A_{j}$

We will ensure optimality of a particular integral solution to (3) by showing the existence of a feasible solution to the dual problem (4) whose dual objective value matches the primal objective value of the intended integral solution - a so-called dual certificate. When the solution of (3) is integral, it is also degenerate, since most of the variables are zero. In fact we experimentally observed that the dual (4) has multiple solutions. Indeed, motivated by this observation and experimental evidence, we can essentially enforce an extra constraint in the dual by asking that the variables $\alpha$ be constant within each cluster. Given $\alpha$’s as such, the $\beta$’s and $\xi$’s are then easily identified. We now formulate a sufficient condition for integrality based on these observations:

Consider sets $A_{1},\ldots,A_{k}$ with $n_{1},\ldots,n_{k}$ points respectively. If $\exists{\alpha_{1},\ldots,\alpha_{k}}$ s.t for each $s\in A_{1}\cup\ldots\cup A_{k}$,

then the k-median LP (3) is integral and the partition in clusters $A_{1},\ldots,A_{k}$ is optimal.

By strong duality, the intended cluster solution is optimal if the corresponding LP objective value

is less than or equal to the dual objective for some feasible point in the dual problem. By restricting the dual variables $\alpha_{q}$ to be constant within each cluster, and by setting $\xi$ to be equal to the RHS of the Lemma statement, we can verify that the dual objective is at least the cost of the intended clustering. Moreover, it is also easy to see that for this setting of $\xi$ and $\alpha_{q}$’s, the dual constraints are trivially satisfied. ∎

Note that the sufficient condition in (5) is similar to the sufficient condition considered in , but turns out to be more powerful in the sense that it allows us to get down to cluster separation $\Delta=2+\epsilon$.

A possible interpretation for the dual variables (which has been exploited by the current primal-dual based approximation algorithms for the $k$-median problem) is as distance thresholds. In the RHS of equation (5) in $\sum_{q\in A_{j}}(\alpha_{j}-d(s,q))_{+}$ a point $s\in P$ gets positive contribution from points $q\in A_{j}$ that are at a distance smaller than $\alpha_{j}$. In this sense, a point in the set $A_{j}$ can only “see” other points within a distance $\alpha_{j}$.

Following this intuition, one way to prove that inequality (5) holds is to show that we can choose feasible dual variables $\alpha_{1},\ldots,\alpha_{k}$ to satisfy

Each center sees exactly its own cluster i.e. $(\alpha_{j}-d(c_{j},q))_{+}>0$ if and only if $q\in A_{j}$.

The RHS of (5) attains its maximum in the centers $c_{1},\ldots,c_{k}$.

Each of the terms $n_{i}\alpha_{i}-\min_{p\in A_{i}}\sum_{q\in A_{i}}d(p,q)$ in the average in the LHS of (5) are the same.

Our strategy is to provide a set of conditions in our data points that guarantee such feasible dual variables exist. Assume the sets $A_{1},\ldots,A_{k}$ are contained in disjoint balls $B_{r_{1}}(c_{1}),\ldots,B_{r_{k}}(c_{k})$ respectively (where we use the notation $B_{r}(c)$ to indicate a ball of radius $r$ centered at $c$), and suppose that $\alpha_{1},\ldots,\alpha_{k},$ $\alpha_{j}>r_{j}$, are such that for all $i\neq j$, $B_{{\alpha}_{j}}(c_{j})\cap B_{r_{i}}(c_{i})=\emptyset$. Given the $\alpha$’s there exist $\tau_{1},\ldots,\tau_{k}>0$ sufficiently small that any $x\in B_{{\tau}_{j}}(c_{j})$ is seen only by points in its own ball (see Definition 3 for a precise statement). We now define conditions on the sets $A_{1},\ldots,A_{k}$ which imply integrality of the linear programming relaxation (3). For simplicity, we assume for the remainder of the section $n_{1}=\ldots=n_{k}=n$ and $r_{1}=\ldots=r_{k}=1$. Roughly speaking, our conditions ask that a) The clusters are separated, being contained in disjoint balls, b) Outside of a certain neighborhood of the center, no point is a good center for its own cluster and c) No point gets too much contribution from any other cluster. More precisely, we require the following separation and center dominance conditions:

Let the sets $A_{1},\ldots,A_{k}$ in $X$, $|A_{1}|=\ldots=|A_{k}|=n$, such that

We say such sets satisfy the separation condition if they are included in $k$ disjoint balls: $A_{1}\subset B_{1}(c_{1})$, …, $A_{k}\subset B_{1}(c_{k})$, $d(c_{i},c_{j})=2+\delta_{ij}$ for $i\neq j$ where $\delta_{ij}>0$, and the distance between $B_{1}(c_{i})$ and $B_{1}(c_{j})$ satisfies:

The expression $\frac{\operatorname{OPT}_{k}-\operatorname{OPT}_{1}}{n}$ provides a way of measuring how different the clusters are from each other. For example, if the clusters are symmetric, then $\frac{\operatorname{OPT}_{k}-\operatorname{OPT}_{1}}{n}=0$. This condition requires bigger separation when clusters are different.

The center dominance condition essentially says that the contribution function attains its maximum in a small neighborhood of the center of each ball, as long as the parameters $\alpha$ are chosen from some small interval.

$A_{1},\ldots,A_{k}$ satisfy center dominance in the interval $(a,b)\subset(1,1+\Theta)$ if

and for all $\alpha_{1},\ldots,\alpha_{k}\in(a,b)$ there exist $\tau_{1},\ldots,\tau_{k}>0$ such that for all $x\in B_{\tau_{j}}(c_{j})$, $j=1,\ldots,k$

Note that, in particular this condition requires the existence of a point of $A_{j}$ in $B_{\tau_{j}}(c_{j})$.

We now state our main recovery theorem, and show that very natural distributions satisfy the conditions.

If $A_{1},\ldots,A_{k}$ are $k$ sets in a metric space $(X,d)$ satisfying separation and center dominance, then there is an integral solution for the k-median LP and it corresponds to separating $P=A_{1}\cup\ldots\cup A_{k}$ in the clusters $A_{1},\ldots,A_{k}$.

The proof of this theorem can be found in Appendix A. The main idea is that given $k$ balls with the same continuous probability distribution, for large values of $n$, the separation condition is just a consequence of the weak law of large numbers. And one can see that center dominance holds in expectation, so it will hold with high probability if the number of points $n$ is large enough. Note that the condition that all measures be the same and rotationally symmetric can be dropped as long as the expectation of the contribution function attains its maximum in a point close enough to the center of the ball and $\lim_{n\to\infty}\frac{\operatorname{OPT}_{k}-\operatorname{OPT}_{1}}{n}<d(c_{i},c_{j})-2$ for all $i\neq j$.

An integrality gap for the k𝑘k-means LP relaxation

We now show that, in contrast to the LP relaxation for the $k$-median clustering problem, the natural LP relaxation for $k$-means does not attain integral solutions for the clustering model presented in Theorem 7, unless the separation between cluster centers exceeds $\Delta=4$. In particular, this shows that the $k$-median LP relaxation performs better (as a clustering criterion) for such data sets.

In an intended integral solution to (10), the variable $z_{pq}=1/|C|$ if $p,q$ belong to the same cluster $C$ in an optimal clustering, and $z_{pq}=0$ otherwise. It is easy to see that such a solution satisfies all the constraints, and that the objective exactly measures the sum of average distances within every cluster. The following theorem shows the LP relaxation cannot recover the optimum $k$-means cluster solution if the distance between any two points in the same cluster is smaller than the distance between any two points in different clusters.

Given a set of points $P=A_{1}\cup\ldots\cup A_{k}$, if the solution of (10) is integral and divides the set $P$ in $k$ clusters $A_{1},\ldots,A_{k}$ then for all $p,q$ in the same cluster $A_{i}$ and $r$ in a different cluster $A_{j}$,

If the solution of (10) is integral and divides the set $P$ in the clusters $A_{1},\ldots,A_{k}$, complementary slackness tells us that

if and only if $\alpha,\beta$ are corresponding optimal dual variables. Combining (11), (13) and (14), since $\beta_{pq}>0$ we obtain that if $p,q$ are in the same cluster and $r$ is in a different cluster,

The result in Theorem 8 is tight in the sense of our distributional model. The following theorem shows separation $\Delta=4$ is a threshold for cluster recovery via $k$-means LP.

For $\Delta<4$ the result in Theorem 8 implies that the solution of the LP will not be the planted clustering with high probability if enough points are provided.

For $\Delta>4$ we show z_{pq}=\left\{\begin{matrix}1/|C|&\text{ ifp,q$belong to the same cluster$C}\\ 0&\text{otherwise}\end{matrix}\right. is the solution of the LP.

If we have feasible $\alpha$’s and $\beta$’s for the dual problem we have $\sum_{q\in P}\beta_{pq}=\xi\;\forall p\in P$ implies $\sum_{p,q\in P}\beta_{pq}z_{pq}=k\xi$; we also have (as a consequence of (13) and the definition of $z_{pq}$) that $\alpha_{p}=\sum_{q\in P}(d^{2}(p,q)+\beta_{pq})z_{pq}$. Then for any dual feasible solution,

Therefore, the existence of a feasible solution for the dual implies that our planted solution is optimal. Then it remains to show that there exists a feasible point for the dual. The solution is generically unique because no constraint in (10) is parallel to the objective function.

Existence of feasible solution of the dual

A feasible solution of the dual is $\{\alpha_{p}\}_{p\in P}$, $\{\beta_{pq}\}_{p,q\in P}$ such that (13), (14) are satisfied together with $\beta_{pq}\geq 0$ for all $p,q\in P$ and $\sum_{q\in P}\beta_{pq}=\xi$ for all $p\in P$. For $p\in P$ let $C_{p}$ its cluster, $|C_{p}|=n$, then summing (13) in $q\in C_{p}$ we get

Let $\textnormal{avg}(p)=\frac{1}{n}\sum_{q\in C_{p}}d^{2}(p,q)$

Let \textnormal{m_{in}}(p)=\max_{q\in C_{p}}d^{2}(p,q) and \textnormal{m_{out}}(p)=\min_{r\not\in C_{p}}d^{2}(p,r). Assuming there exists a feasible point for the dual we know the solution for the LP is integral (i.e. our planted clustering) then we know (15) holds. In other words:

Then, a feasible solution for the dual problem exists if there exists $\xi$ that satisfies (16) for all $p\in P$. A sufficient condition is:

Since this condition does not depend on the position of the cluster we can assume that the cluster $C_{r}$ where the LHS is maximized is centered in 0. Let f(r)=\textnormal{m_{in}}(r)-\textnormal{avg}(r)=\frac{1}{n}\sum_{l\in C_{r}}\|r-\textnormal{m_{in}}(r)\|^{2}-\|r-l\|^{2}. In order to find its maximum consider

But \textnormal{m_{in}}(r)\neq 0 for all $r\in P$ since the center of the cluster cannot maximize the distance square (unless the trivial case where all the points in the cluster coincide with the center). Then $f$ is maximized in the boundary of the unit ball. Then we need

which holds for $\Delta>4$ with high probability when $n\to\infty$ since the points come from a rotationally symmetric distribution. ∎

Integrality for the k𝑘k-means SDP relaxation

The idea is to construct a dual certificate and find deterministic conditions for the SDP to recover the planted clusters. Then we check for what separation the conditions are satisfied with high probability using bounds on the spectra of random matrices. We explain the general idea in this section and we present full proofs in Appendix C and D.

Recall the dual certificate approach: if we can construct a set of feasible dual variables $(z,\alpha,\beta,Q)$ with dual objective function (18) equal to the primal objective (17) corresponding to $X$, then we can be assured that $X$ is an optimal solution. If, in addition, $\operatorname{rank}(Q)+\operatorname{rank}(X)=N$, then we can be assured that $X$ is the unique optimal solution. Towards this end, complementary slackness tells us that $QX=0$, which means that

Complementary slackness also tells us that, over each $n\times n$ diagonal block,

We thus have, for each $n\times n$ diagonal block of $Q$,

Note that here $e_{i}$ are $n$-length vectors and before they were $N$-length (we shall switch between vectors of length $n$ and $N$ when necessary, this makes our notations easier).

In fact, these constraints implied by complementary slackness suffice to specify the $\alpha_{(a,i)}$ values. Since the total dual objective is equal to the clustering cost of the intended solution, it remains to complete the $Q$ matrix and the $\beta$ matrix such that $\beta\geq 0$ (entry wise), and $Q\succeq 0$ (in the positive definite sense). To this end, consider the non-diagonal $n\times n$ blocks:

Since we want to ultimately arrive at a sufficient condition for integrality which depends on within- and between-cluster pairwise distances, and we know that $Q$ must be positive semi-definite and satisfy the constraints (19), we impose a slightly stronger condition on the off-diagonal submatrices $Q^{(a,b)}$ ($a\neq b$) which will imply all required constraints on $Q$: we set

Writing $Q^{(a,b)}$ also in terms of the $\beta^{(a,b)}$ and solving for $\beta^{(a,b)}$, the non-negativity of $\beta$ gives us the following constraints that these parameters need to satisfy: for all clusters $a\neq b$, and all $r\in a,s\in b$,

Notice that the above constraints essentially compare (for two points $r,s$ in clusters $a,b$ respectively) (i) the average distance of $r$ to the cluster $b$, the average distance of $s$ to cluster $a$, the distance between $r$ and $s$, and finally the average distance between the two clusters, indicating that these are reasonable conditions. Now, note by (21) that $Q\succeq 0$ automatically holds once $z$ is sufficiently large; It remains to find a lower bound on $z$ for which this holds. Since $Q1_{a}=0$ for all $a$, it is sufficient to check that $x^{T}Qx\geq 0$ for all $x$ perpendicular to $\Lambda$; that is, for all $x$ in the span of $\{1_{a}\,,\,a\in[k]\}$. But if $x$ is perpendicular to these cluster indicator vectors, $x^{T}Qx\geq 0$ greatly simplifies tothis uses our choice of $Q^{(a,b)}$ above, which ensures that most terms cancel $zx^{T}x+2x^{T}(\sum_{a}D^{(a,a)})x-x^{T}Dx>0$. This suggests setting $z>z^{\ast}=\left(2\max_{a}\max_{x\perp 1}\left|\frac{x^{T}D^{(a,a)})x}{x^{T}x}\right|+\max_{x\perp\Lambda}\left|\frac{x^{T}Dx}{x^{T}x}\right|\right)$, so that the null space of $Q$ only consists of $\Lambda$, thus ensuring that $\operatorname{rank}(Q)+\operatorname{rank}(X)=N$. Decompose the squared euclidean distance matrix $D=V+V^{T}-2MM^{T}$ where $V$ has constant rows, every entry of row $i$ is equal to the squared norm of $x_{i}$, and the $i$th row of $M$ correspond to the actual coordinates of the point $x_{i}$. Then by observing that $x^{T}(V+V^{T})x=0$ for $x\perp\Lambda$ and that $MM^{T}$ is positive semidefinite we can instead set $z>z^{\ast}=4\max_{a}\max_{x\perp 1}\frac{x^{T}M^{(a)}M^{(a)T}x}{x^{T}x}$. This combined with the non-negativity of $\beta$ gives us the following deterministic separation condition:

A clustering instance satisfies average separation if for all clusters $a,b$, and all $r\in a,s\in b$:

where $z^{\ast}=4\max_{a}\max_{x\perp 1}\frac{x^{T}M^{(a)}M^{(a)T}x}{x^{T}x}$.

The above condition essentially compares (for two points $r,s$ in clusters $a,b$ respectively) (i) the average distance of $r$ to the cluster $b$, the average distance of $s$ to cluster $a$, the distance between $r$ and $s$, and finally the average distance between the two clusters. Using the parallelogram identity this condition can be greatly simplified to:

For cluster $c$ define $x_{c}=\sum_{y\in c}y$ the mean of the cluster. A clustering instance satisfies average separation if, for all clusters $a\neq b$ and for all indices $r,s$ we have

If a euclidean clustering instance with the squared distance matrix $D$ satisfies average separation as defined above, then the corresponding $k$-means SDP for the instance has unique integral solution equal to the $k$-means optimal solution, and corresponding to this clustering.

In Appendix D we show that for our distributional instances consisting of clusters whose centers are separated by at least $2\sqrt{2}(1+\sqrt{1/m})$, average separation is satisfied for large enough $n$. Putting this together, we get the following:

Where convex relaxations succeed, Lloyd’s Method can fail

The well-known heuristic algorithm for solving the $k$-means optimization problem known as Lloyd’s algorithm We recap how the Lloyds algorithm proceeds: initialize $k$ centers uniformly at random from among the data points. Then, in each iteration, two steps occur: (i) using the currently chosen centers, each point assigns itself to the nearest center; (ii) now, given the assignment of data points to clusters, new centers are computed as being the means of each cluster (i.e., the average of the data points assigned to a cluster). The algorithm terminates at the first step when the clustering does not change in successive iterations. (also known as the $k$-means algorithm or Voronoi iteration) can fail to find global optimum solutions in the setting of separated isotropic clusters where, as shown in Theorem 7 and Theorem 11 respectively, the $k$-median LP and $k$-means SDP are integral. The construction of a bad scenario for Lloyd’s algorithm consists of $3$ balls of unit radius, such that the centers of the first two are at a distance of $\Delta>2$ from each other, and the center of the third is far away (at a distance of $D\gg\Delta$ from each of the first two balls). Generate the data by sampling $n$ points from each of these balls. Now we create $l$ copies of this group of $3$ clusters such that each copy is very far from other copies. We will show that with overwhelming probability Lloyd’s algorithm will pick initial centers such that either (1) some group of 3 clusters does not get 3 centers initially, or (2) some group of 3 clusters will get 3 centers in the following configuration: 2 centers in the far away cluster and only one center in the two nearby clusters. In such a case it is easy to see the the algorithm will never recover the true clustering.

The same example can also be extended to show that the well known kmeans++ algorithm which uses a clever initialization will also fail with high probability when the number of clusters and the dimension of the space is large enough, even in the setting with overseeding proposed in . In particular, we prove the following theorem in Appendix E.

Given an overseeding parameter $c>1$ and minimum separation $\Delta>2$, there exist inputs with center separation at least $\Delta$ for which kmeans++, overseeded with $ck$ initial centers, fails with high probability to exactly recover the clusters.

Simulations

If instead of requiring integrality and recovery of the planted clusters, we only test for integrality (i.e. the result of the simulation should just be some clustering, not necessarily the clustering corresponding to the disjoint supports from which we draw the points) we see a very interesting but distinct behavior of the phase diagrams:

We observe that $k$-median LP obtains integral solutions on every instance of our experiments. That is, the failure instances in our experiments shown in Figures 4 and 4 still coincide with clusterings, just not the clusters corresponding to the planted disjoint supports. Indeed, a different clustering can make sense as being more “optimal” than the planted distribution when $N$ is small. We refer to Section 7 for a discussion of an open problem regarding this.

For all instances of our experiments, every time we obtain an integral solution, the integral solution corresponded to the underlying expected clustering. The failure instances in Figures 4 and 4 correspond to matrices that do not represent any clustering as represented in Figure 5. We have not explored whether it is possible to recover the expected clustering via rounding such a fractional solution.

Conclusions and Future work

In this work we studied convex relaxations for popular clustering objectives and gave sufficient deterministic conditions under which such relaxations lead to exact recovery thereby bypassing the traditional rounding step in approximation algorithms. Our results also shed light on differences between different relaxations. For instance, our theoretical and empirical results show that the $k$-median LP is much better at recovering optimal solutions than the $k$-means LP. In fact, we show that the $k$-means LP is integral only in the regime $\Delta\geq 4$ where a simple thresholding algorithm could also be used to distinguish clusters.

Our analysis for the $k$-median LP shows that for any separation $2+\epsilon$ and any number of clusters $k$, the solution of the $k$-median LP is the planted clusters with high probability if $n$ is large enough. It remains to quantify how large $n$ needs to be in terms of the other parameters.

In contrast, for the $k$-means SDP shows that for center separation $\Delta\geq 2\sqrt{2}(1+\sqrt{1/m})$, the solution corresponds to the planted clusters with high probability for $n$ sufficiently large, where we give a precise bound on $n$. We conjecture the same result should hold for separation $\Delta>2+\epsilon$ with high probability.

Several possible future research directions come out of this work. Although we study only a specific distribution over data – points drawn i.i.d. from disjoint balls of equal radius – it is of interest to investigate further to determine if the exact recovery trends we observe are more general, for example, by relaxing certain assumptions such as equal radii, equal numbers of points within clusters, etc. A particularly interesting direction is the setting where the balls overlap and/or when the points are drawn according to a mixture of Gaussians. These two examples share the difficulty that there is no longer a “ground truth” clustering to recover, and hence it is not even clear how to build a dual certificate to certify an integral solution. Despite this difficulty, we observe in experiments that the $k$-median LP relaxation still remains integral with high probability, even in extreme situations such as when the points are drawn i.i.d from a single isotropic distribution but parameter $k>1$ clusters are sought in the LP relaxation. As in most practical applications, hoping for ground truth recovery is overly optimistic; understanding the integrality phenomenon beyond the exact recovery setting is an important problem. Recently, the same phenomenon was observed in the context of the Procrustes, alignment, and angular synchronization problems and referred to as rank recovery.

A third direction would be to relax the notion of integrality, asking instead that a convex relaxation produce a near-optimal solution. There has been recent work on this for the $k$-means++ algorithm . Another by-product of our analysis is a sufficient condition under which the primal-dual algorithm for $k$-median leads to exact recovery. It would be interesting to prove similar exact recovery guarantees for other approximation algorithms.

Finally, convex relaxations are a very powerful tool not just for clustering problems but in many other domains. The questions that we have asked in this paper can also be studied for various other domains such as inference in graphical models , graph partitioning , and more.

Acknowledgements

We would like to thank Ulas Ayaz, Dustin Mixon, Abhinav Nellore and Jesse Peterson along with the anonymous referees for helpful comments and corrections which greatly improved this paper. Part of this work was done while ASB and RW were participating in Oberwolfach’s workshop “Mathematical Physics meets Sparse Recovery”; these authors thank Oberwolfach’s hospitality.

References

Appendix A Proof of Theorem 6

If $A_{1},\ldots,A_{k}$ are $k$ sets in a metric space $(X,d)$ satisfying separation and center dominance, then there is an integral solution for the k-median LP and it corresponds to separating $P=A_{1}\cup\ldots\cup A_{k}$ in the clusters $A_{1},\ldots,A_{k}$.

Recall Lemma 5. We need to show there exists ${\alpha_{1},\ldots,\alpha_{k}}$ such that for each $s\in A_{1}\cup\ldots\cup A_{k}$ equation (5) holds:

First, note that by the center dominance property (Definition 3), that among all points within a cluster $A_{j}$, the maximum RHS is attained for $s\in B_{\tau_{j}}(c_{j})$, i.e., for $s$ in a small ball around $c_{j}$. Moreover, from the separation property (Definition 2), it is easy to see that points in $B_{\tau_{j}}(c_{j})$ don’t receive any contribution (in the LHS) from points in other clusters, therefore the following holds:

Now, the RHS of (5) maximizes $s$ over all clusters $j$, so we additionally enforce:

Under this condition, it is easy to see that (5) holds for all $s\in A_{1}\cup\ldots\cup A_{k}$. Since the points and the sets are given, this is a system of linear equations with one degree of freedom.

Appendix B Proof of theorem 7

The proof of this theorem consists of showing that separation and central dominance conditions holds with high probability when the points are drawn from the distribution specified in the theorem statement.

We need to show that for some $\alpha_{1},\ldots,\alpha_{k}$ satisfying (27) the maximum of $\left\{P^{(\alpha_{1},\ldots,\alpha_{k})}(x_{i}^{(j)})\right\}_{i=1}^{n}$ is attained in some $x_{i}^{(j)}\in B_{\tau_{j}}(c_{j})$ for every $j=1,\ldots,k$ with high probability.

The proof is done in Lemma 13. This is the step where we use that the measure is rotationally symmetric. In fact, this assumption is not strictly needed: any continuous probability distribution that satisfies the thesis of Step 1 and has positive probability in every neighborhood of the center would guarantee asymptotic recovery.

The weak law of large numbers implies that for all $i,j\in\{1,\ldots,k\}$, the random variable $\frac{\operatorname{OPT}_{i}-\operatorname{OPT}_{j}}{n}$ converges to zero in probability, i.e.:

Define $\alpha(z)>1$ the maximum value of alpha such that $B_{\alpha}(z)\cap\bigcup_{i\neq j}B_{1}(c_{i})$ can be copied isometrically inside $B_{1}(c_{j})$ along the boundary without intersecting each other and without intersecting $B_{\alpha}(z)$ as demonstrated in Figure 6. Let $\alpha=\max\{\alpha(z):z\in\cup_{j=1}^{k}B_{1}(c_{j})\}$. We know $\alpha>1$ since the balls are separated: $d(c_{i},c_{j})>2$ whenever $i\neq j$.

Then the maximum of $P^{(\alpha_{1},\ldots,\alpha_{k})}(x_{1}^{(j)}),\dots,P^{(\alpha_{1},\ldots,\alpha_{k})}(x_{n}^{(j)})$ is attained for an $x_{s}^{(j)}$ in $B_{\tau_{j}}(c_{j})$ with probability at least $\beta(n)$ where $\lim_{n}\beta(n)=1$.

Let $M$ such that $0<P_{i}^{(\alpha_{1},\ldots,\alpha_{k})}(z)<M$. Then we use Hoeffding’s inequality,

With high probability, the bigger $P^{(\alpha_{1},\ldots,\alpha_{k})}(z)$ is for $z$ outside $B_{\tau_{j}}(c_{j}),$ the smaller the same function can be for $z\in B_{\tau}(c_{j})$. In other words, if $x\in B_{\tau}(0)$ and $x^{\prime}\in B_{1}(c_{j})\backslash B_{\tau_{j}}(c_{j})$

Appendix C Exact recovery using the k𝑘k-means SDP

The setting is that we have $k$ clusters, each of size $n$, so a total of $N=kn$ points. We index a point with $(a,i)$ where $a=1,\dots,k$ represents the cluster and $i=1,\dots,n$ the index of the point in that cluster. The distance between two points is represented by $d_{(a,i),(b,j)}$. We define the $N\times N$ matrix $D$ given by the squares of these distances. It consists of blocks $D^{(a,b)}$ of size $n\times n$ such that $D^{(a,b)}_{ij}=d_{(a,i),(b,j)}^{2}$.

The intended solution is $X$ which is $1/n$ in the diagonal blocks and otherwise. Defining $1_{a}$ as the indicator function of cluster $a$ the intended solution is

We want to construct a dual certificate to show that this solution is the only optimal solution.

We thus have, for the diagonal blocks of $Q$,

note that here $e_{i}$ are $n$-length vectors and before they were $N$-length.

Summing this expression over all $r=1,\dots,n$ we get

Our dual certificate will satisfy equalities (33). Note that summing (33) over $a$ and $r$ gives

which states that the objective value of the dual solution matches the objective value of the intended primal solution. By ensuring that the null space of $Q$ only consists of linear combinations of the vectors $1_{a}$ we can get a uniqueness result.

Suppose there exists $z$ and $\beta^{a,b}$ such that $\beta^{a,b}\geq 0,a\neq b$. Define $\alpha_{a,r}$ as

Then if $Q^{(a,b)}1=0$, $Q\succeq 0$ and the nullspace of $Q$ has dimension exactly $k$, the k-means SDP has a unique solution and is the intended cluster solution.

Let us rewrite $Q$ in terms of $z$ and $\beta$. We have

With a bit of foresight, we now impose a condition on $Q$ that implies the conditions in this Lemma. We will require that

Note that $Q^{(a,b)}1=0$ and $Q^{(b,a)}1=Q{(a,b)}^{T}1=0$. This means that we will require, $\forall r,s$, that

This is satisfied for non-negative $\beta$’s precisely when

By construction, $Q^{(a,b)}1=0\quad\forall_{a,b}$ so we just need to ensure that, for all $x$ perpendicular to the subspace $\Lambda$ spanned by $\{1^{(a)}\}_{a=1}^{k}$ that

Since in particular $x\perp 1$, as a consequence of (35) and (37) the expression greatly simplifies to:

Now, we can decompose the squared euclidean distance matrix $D$ as

Since we need the existence of a $z$ to satisfy both (43) and (39) we need that $\forall_{a\neq b}\forall_{r,s}$,

This gives us the main Lemma of this section:

If, for all clusters $a\neq b$ and for all indices $r,s$ we have

then the k-means SDP has a unique solution and it coincides with the intended cluster solution.

For cluster $c$ define $x_{c}=\sum_{y\in c}y$ the mean of the cluster. By using the parallelogram identity in (45) one can rewrite the condition of Lemma 17.

If, for all clusters $a\neq b$ and for all indices $r,s$ we have

then the k-means SDP has a unique solution and it coincides with the intended cluster solution.

The question remains: what is the necessary minimal separation between clusters so that the conditions (45) or (46) are satisfied. In the next subsection, we will make this statement more precise for a general class of probabilistic models for clusters.

Appendix D The k𝑘k-means SDP distinguishes clusters

In this section we consider a probabilistic models for clusters. For simplicity, we assume in this section that the number of points in each cluster is the same and the radii of all clusters are the same and equal to 1.

If clusters $a$ and $b$ are supported in two disjoint euclidean balls and their respective means $x_{a}$ and $x_{b}$ are the centers of their respective balls, then the LHS of (46) has minimum

In particular it is positive for center separation $\Delta>2\sqrt{2}$.

By using Lagrange multipliers one finds that if $\Delta\leq 4$ then the minimum is attained at points such that $x_{r(1)}=\Delta/4$, $x_{s(1)}=\Delta/2$ and $x_{r(i)}=x_{s(i)}$ for all $i=2,\ldots,m$. When $\Delta>4$ the minimum is attained in $x_{r}=(1,0,\ldots,0),\;x_{s}=(\Delta-1,0,\ldots,0)$. By substituting in (46) we obtain the desired result. ∎

Recall that $\Lambda$ is the $k$-dimensional subspace spanned by $\{1^{(a)}\}_{a=1}^{k}.$ Since $C^{T}z=0$ for $z\perp\Lambda$ we have,

where $c>0$ is an absolute constant. Taking $t=s\sqrt{\frac{n\theta}{m}}$, we find that $\frac{4}{n}\sigma_{\max}(\widetilde{M}^{(a)})^{2}\leq 4\theta(1+s)^{2}\frac{1}{m}$ with probability at least $1-2m\exp(-cns^{2}/m).$

with probability exceeding $1-2mk\exp(-cns^{2}/m)$

We conclude that the inequality in (46) sufficient for integrality of the $k$-means SDP is satisfied with probability exceeding $1-2mk\exp(-cns^{2}/m)$ if

which holds once the centers of the clusters are separated by euclidean distance $\Delta>\sqrt{8(1+s)^{2}\frac{\theta}{m}+8}$.

Fixing parameter $s=\frac{1}{\log n},$ the above analysis implies the following theorem.

In the limit $n\rightarrow\infty$, the probability of success goes to 1 and the separation distance goes to $2\sqrt{2}(1+\sqrt{\frac{\theta}{m}})$.

Appendix E Where convex relaxations succeed, Lloyd’s Method can fail

As mentioned in Section 5, it is not difficult to construct a bad scenario for Lloyd’s $k$-means algorithm; consider $3$ balls $A$, $B,$ and $C$ of unit radius such that the centers of $A$ and $B$ are at a distance of $\Delta>2$ from each other, and the center of $C$ is far away (at a distance of $D\gg\Delta$ from each of the first two balls). Generate data by sampling $n$ points from each of these balls. Now consider this group of $3$ clusters as a unit, and create $l$ copies $i=1,\ldots,l$ of such units, $\{A_{i},B_{i},C_{i}\},$ such that each group $i$ is sufficiently far from others. We will show that with overwhelming probability, Lloyd’s algorithm picks initial centers such that either (1) some group of 3 clusters does not get 3 centers initially (i.e. there exists $i$ such that there are fewer than 3 centers among $A_{i}$, $B_{i}$, $C_{i}$), or (2) some group of 3 clusters $i$ will get 3 centers in the following configuration: 2 centers in $C_{i}$ and 1 center in $A_{i}\cup B_{i}$. In such case, it is easy to see the the algorithm cannot recover the true clustering. The same example can also be extended to show that the well known kmeans++ algorithm which uses a clever initialization will also fail.

We first analyze a single group of $3$ clusters $A_{i}$, $B_{i}$, $C_{i}$. Since Lloyd’s method chooses the initial centers at random, there is a constant probability event of two centers being chosen from $C_{i}$, and only one center chosen among the first two balls. The probability of this event is $\frac{2}{9}$. Now consider any iteration where two centers $p,q$ lie in the $C_{i}$ and only one center $r$ lies in $A_{i}\cup B_{i}$. The first step of Lloyd’s method computes new clusters by assigning each point to the nearest current center. Note that because $C_{i}$ is far away from $A_{i}$ and $B_{i}$, each point in the first two balls still gets assigned to the center $r$, and the data points from the third ball get assigned to either $p$ or $q$. Then, when the new centers are computed (by taking the average of the newly formed clusters), once again there will be two centers lying in $C_{i}$, and only one center from $A_{i}\cup B_{i}$.

Inductively, we can conclude that, if the random assignment of centers in the first iteration chooses two centers from $C_{i}$, then the final clustering will also have two centers from $C_{i}$. Consequently, the clustering will not be optimal. Therefore, this example shows that the Lloyds method fails with constant probability.

Failure of kmeans++: There exist configurations for which kmeans++ fail with high probability, even its versions with overseeding and pruning. Let’s take for instance the algorithm from , that consists in $k$-means preceded by the following initialization

Given an overseeding parameter $c>1$, sample $ck$ points as centers with the following distribution: if $Z=\{c_{1},\ldots,c_{j}\}$ are centers the probability of $x$ being added to the set of centers is proportional to $\min_{c_{i}\in Z}\|x-c_{i}\|^{2}$.

While we have more than $k$ centers, greedily remove a center from $Z$ which leads to the minimum increase in the $k$-means cost.

The argument we use to show the failure of Lloyd’s algorithm can be adjusted to this setting. Let’s say we have $3k$ clusters arranged in groups of three $\{A_{i},B_{i},C_{i}\}_{i=1}^{k}$ such that the groups are far apart from each other and in each group the clusters $A_{i}$ and $B_{i}$ are very close to each other and $C_{i}$ is far away as before. If after the seeding step there is only one center among $A_{i}\cup B_{i}$ for any $i\in\{1,\ldots,k\}$, then the algorithm deterministically fails in recovering the clusters. The idea is illustrated in figures 9 and 9.

We show that given $c>1$, $\Delta>2$ and $0<\gamma<1$ one can choose $K=3k$ centers such that the minimum distance between any two of them is $\Delta$ and the probability of failure of kmeans++ with overseeding and pruning is at least $\gamma$.

We can bound the probability of selecting zero centers at $A_{1}$ and one center at $B_{1}$. Each time we select a center, the probability of not selecting a center in $A_{1}\cup B_{1}$ is greater than the probability of not selecting it given that there is one center at $B_{1}$ and there is at least one center in the rest of the balls. For that case,

If $x\in A_{1}$ then $\min_{c_{i}\in Z}\|x-c_{i}\|^{2}<(2+\Delta)^{2}<4\Delta^{2}$.

If $x\in B_{1}$ then $\min_{c_{i}\in Z}\|x-c_{i}\|^{2}<4$.

If $x$ in a cluster $X$ different from $A_{1}$ and $B_{1}$ then our dimensionality assumption implies $\min_{c_{i}\in C}\|x-c_{i}\|^{2}>1/4$ for at least half of the volume of $X$.

Then, after the normalization, if $K$ is large enough the probability of selecting $cK$ centers such that there is exactly one at $A_{1}\cup B_{1}$ is at least

Then, if we let $K$ be in the order of $\exp(c\Delta^{\prime})$, the probability of having exactly one center in $A_{i}\cup B_{i}$ for $i=1,\ldots k$ can be made arbitrarily close to 1.

Appendix F Recovery guarantees through Primal-Dual algorithm

As mentioned in the introduction our results for the $k$-median LP also imply that the Primal-Dual algorithm of Jain and Vazirani converges to the exact solution whenever separation and center dominance conditions are satisfied.

In the primal-dual based algorithm, $T$ is the set of medians and $S$ is the set of points that have not been assigned to a median yet. The parameter $z$ plays the role of the cost of setting a median. We can see the dual variable $\alpha_{j}$ as the amount point $j\in P$ will pay for the solution; a $\beta_{ij}$ can be thought as the amount $j\in P$ is willing to pay to have $i\in P$ as a median. The algorithm increases the dual variables until some median $i$ is paid off. When that happens, $i$ is assigned as a median, and the algorithm freezes the set of points that contributed to $i$.

When all points had been assigned to medians, the algorithm assures that no point is paying for two different medians by iteratively selecting one element from $T$ and removing all other elements that share contributors with it. This removing phase is what makes this an approximation algorithm. If no point contributes to two different medians in $T$, then the solution given by this algorithm is exact.

Let $A$ and $B$ be defined as in Section 2. In Theorem 6 we proved not only that the LP (3) has an integral solution but also that there is a solution to the dual problem (4) with the dual variables constant within each cluster. This suggests that the primal-dual algorithm will freeze all the points in one cluster at once when $z$ is chosen to be the solution to (3) (and (4)).

Let’s say $\alpha_{A}<\alpha_{B}$. When all $\alpha_{j}$ ($j\in P$) get to be $\alpha_{A}$ then $m_{A}$ becomes a center and all points in $A$ freeze. This occurs because if $k\in A$ then the RHS of (5) attains its maximum (equal to $z$) in the median $m_{A}$. Then we have

Since $d(m_{A},i)>\alpha_{B}>\alpha_{A}$ for all $i\in B$, no point from $B$ contributes to $m_{A}$. After all points in $A$ freeze, when the remaining $\alpha$ reach $\alpha_{B},$ the rest of the points freeze and $m_{B}$ becomes their median. For $k\in B$ and $j\in A$, ($j\neq m_{A}$) $\beta_{kj}=(\alpha_{A}-d(k,j))_{+}$ since it has not increased once $m_{A}$ is a median. For $j=m_{A}$ we have $(\alpha_{B}-d(k,m_{A}))_{+}=0=(\alpha_{A}-d(k,m_{A}))_{+}$. Then

If $A$ and $B$ are two sets satisfying separation and center dominance conditions, then the primal-dual algorithm with parameters $P=A\cup B$ and $z=n\alpha_{A}-\operatorname{OPT}_{A}=n\alpha_{B}-\operatorname{OPT}_{B}$ assigns $x_{A}$ to $m_{A}$ for all $x_{A}\in A$ and $x_{B}$ to $m_{B}$ for all $x_{B}\in m_{B}$.