<p>The constant does tend to 1/2 as the dimension increases. In d dimensions, you can have d+1 points at distance one from each other, so the the sum of distance-squared is ${d+1 \choose 2}$ and the maximum cut is at most $(d+1)^2/4$, which is a $\frac 12 \cdot \frac {d+1}{d}$ fraction of the total weight</p>

CC BY-SA 2.5
2011-03-15T17:28:35.017Z
@Suresh: What I was really after is proving that you *can* do better in low dimensions, i.e. I'm interested in the sequence of actual values of the worst constants for particular low d's.
Milos Hasan
CC BY-SA 2.5
2011-03-15T17:47:11.223Z
I really wanted to prove an actual gap between 1/2 and 2/3 for low d. This would have interesting consequences, i.e. that you can beat Monte Carlo summation/integration (by splitting your problem into sub-problems smartly instead of randomly), if your problem is intrinsically low-dimensional (any many are).
Milos Hasan
CC BY-SA 2.5
2011-03-15T19:06:10.223Z
Although this is only an answer for large d, it shows what kind of difficulties can come up in the analysis of the small-d case. Suppose that, in 2 dimensions, you could have five points whose pairwise distance-squared are all between 1 and 1.1. Then the total weight is at least 10 and the max cut is at most 6.6. If 2/3 is the right answer for two dimensions, you have to be able to show that if you have five points such that all the pairwise euclidean distances are at least one, one of the pairwise euclidean distances is at least $\sqrt {1.1}$. How do you argue that?
Luca Trevisan
CC BY-SA 2.5
2011-03-15T20:22:52.683Z
There is something about low dimensions that makes it impossible to find many points that are almost equally far from each other, but may indeed be too difficult to get a handle on. Could we instead address the case where $d$ is small but $k$ is large? If you pick $n$ points uniformly within the square $[0,1]^2$, and subdivide the square into $\sqrt{k} \times \sqrt{k}$ bins, then only $\frac{1}{k^2}$ edges will remain uncut on average - much better than the $\frac 1 k$ you'd get by random clustering. When the points are not chosen uniformly at random, can you still cut $1 - \frac{1}{k^2}$?
Milos Hasan
CC BY-SA 2.5
2011-03-15T20:37:52.700Z
Correction: above should be $\frac{2}{k^2}$ instead of $\frac{1}{k^2}$ - since the largest weight edge that fits into a bin is $\frac 2 k$.
Milos Hasan
CC BY-SA 2.5
2011-03-16T01:45:47.507Z
it could be that your sets splits into 3 groups, each of k/3 points, and each group is concentrated around one the vertices of a equilateral triangle, giving you the 2/3 bound that you conjecture to be the worst case
Luca Trevisan
CC BY-SA 2.5
2011-03-16T03:48:07.477Z
@Luca: Sorry for some confusion in notation, I'm using $k$ as the number of clusters (as in max-$k$-cut) and $n$ as the number of points. A random partition into $k$ clusters will give you cut weight of $1 - 1/k$, but my binning argument above suggests that $1 - O(k^{-2})$ might be possible in the plane (or more generally $1 - O(k^{-1-2/d})$ in $d$ dimensions.) Does that sound plausible?
Milos Hasan
CC BY-SA 2.5
2011-03-16T05:23:12.947Z
Oh, I see. That's another very interesting and very difficult question. It would be enough to show that, for any $n$ points for which the average distance-squared is 1 we can find a partition of them into $k$ subsets such that each subset has $O(n/k)$ points, and each subset has euclidean diameter $O(1/\sqrt{k})$. In the special case in which (after the normalization that makes the average distance-squared 1) the points are contained in a disk of radius-squared O(1), it is true
Luca Trevisan
CC BY-SA 2.5
2011-03-16T05:28:30.917Z
Because you can cover the disk of radius $O(1)$ with $O(t)$ squares of euclidean size $1/\sqrt{t} \times 1/\sqrt {t}$ (we'll pick $t$ in a minute), and then you can come up with a partition of the points in the following way: if a square has $\leq 2n/k$ points, then the points in the square are an element of the partition; otherwise, we arbitrarily divide the point in a square into subsets of size $\leq 2n/k$ each. So the number of sets that we end up with is at most $O(t)$ + $n/(2n/k)$ which is at most $O(t)$ + $k/2$ which is at most $k$ for a proper choice of $t=\Theta(k)$
Luca Trevisan
CC BY-SA 2.5
2011-03-16T21:27:06.240Z
Excellent! So if some bins are empty, and others have more than a "fair" share of points, it does not pose a problem. It seems that to prove that the uncut weight is $O(k^{-2})$, you just need to move the points (by affine transformation) into the unit square - no need to worry about normalization of the average weight, since that will only affect the constant in the O() notation.
Milos Hasan
CC BY-SA 2.5
2011-03-17T00:09:02.470Z
I don't see how you would do it in general. The approach seems to require that the average distance-squared is at least a constant fraction of the maximum distance-squared, which is not true in general.
Luca Trevisan
CC BY-SA 2.5
2011-03-17T00:48:17.757Z
Oh, I see. We need to prove that the uncut weight is $O(k^{-2})$, where the constant is independent of $n$.
Milos Hasan
CC BY-SA 2.5
2011-03-15T08:25:45.270Z
OK, but why does the configuration of d+1 points at a distance 1 from each other constitute the worst case? This seems plausible, but is it obvious? (And for d = 1, two points at a distance 1 from each other are clearly not the worst case; the 6-point configuration you gave above is worse. Could it be that d = 1 is the only pathological case, and it works for d >= 2?)
Milos Hasan
CC BY-SA 2.5
2011-03-15T10:16:19.100Z
@milos I'm not sure I understand. we know that 0.5 is achievable, and this example shows that you can't do better. It doesn't however break the 2/3 conjecture for the plane though.
Suresh Venkat
CC BY-SA 2.5
2011-03-15T07:38:35.597Z
2011-03-15T07:38:35.597Z
Luca Trevisan
<p>Take 3 points A, B, C on an equilateral triangle and add 3 more points D, E, F, in the center. It's clear you want two of A, B, C on one side of the cut, so let's say the cut on these three points is (AB;C). Now, each of the points D, E, F has to go on the C side of the cut, so the optimal cut is (AB; CDEF), and the ratio is easily checked to be 2/3.</p>

<p>Now, move each of the points D, E, F slightly away from the center to form a small equilateral triangle. It doesn't matter in which direction, as long as they're symmetric around the center. If you move them a small enough distance, the optimal cut still has to be (AB; CDEF). Consider the length of this cut. The edges (AC, BC) form 2/3 of the total length of the edges (AB, BC, AC). By symmetry, the total length  of the edges (AD, AE, AF, BD, BE, BF) are 2/3 of the length of the edges (AD, AE, AF, BD, BE, BF, CD, CE, CF). But <em>none</em> of the edges (DE, EF, DF) are in the cut. So the ratio of this cut is strictly less than 2/3.</p>

<p>You should be able to optimize this construction to find a configuration where the optimal cut is significantly less than 2/3.  Trying it, I get that if you take six points arranged in two equilateral triangles having the same center, with the smaller one $(\sqrt{6}-1)/5 \approx .2899$ the size of the larger one, then the max-cut becomes $.6408$ the total weight instead of $2/3$.</p>

CC BY-SA 2.5
2011-03-20T22:12:24.230Z
Nice, you're right! Well, another elegant conjecture bites the dust... It's still an open question though whether the constant in the plane is larger than 1/2, or whether you can achieve $1 - O(k^{-\alpha})$ with $k$ clusters, where $\alpha > 1$. I'll think about it more.
Milos Hasan
CC BY-SA 2.5
2011-03-20T22:55:18.437Z
My guess is that the right answer is something not too much lower than .64, but I have no idea how to go about showing a lower bound.
Peter Shor 
CC BY-SA 2.5
2011-03-19T15:15:16.327Z
2011-03-20T03:40:27.050Z
2011-03-20T03:40:27.050Z
Peter Shor 
<p>Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that is at least $\frac 2 3$ of the total weight? If not, which constant should replace the $\frac 2 3$?</p>

<p>The worst example I'm able to find is 3 points on an equilateral triangle, which achieves the $\frac 2 3$. Note that a random split would produce $\frac 1 2$, but it seems intuitively obvious that in low dimensions, one can cluster better than randomly.</p>

<p>What happens for max-k-cut for k > 2? How about a dimension d > 2? Is there a framework to answer such questions? I know about Cheeger's inequalities, but those apply to sparsest cut (not max-cut) and only work for regular graphs.</p>

<p>(Question is inspired by the problem of clustering light sources in computer graphics to minimize variance).</p>

CC BY-SA 2.5
2011-03-14T10:57:18.720Z
There is a simple 1-2/k approximation for Max k-Cut, and for k>2 you can find a good big cut but for k=2 you can see http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf and related topics, I think if you find a good cut with hi probability you can say there is a cut with 2/3 or not, at least the range of possibility will be limited.
Saeed
CC BY-SA 2.5
2011-03-14T11:53:30.260Z
Saeed, the Goemans-Williamson paper gives an algorithm that finds a cut with a good ratio to the optimum, but what is the ratio of the optimum to the total edge weight? On general graphs, this can be as low as $\frac 1 2$, but if the edge weights are squared distances in low dimensions, can it be higher?
Milos Hasan
CC BY-SA 2.5
2011-03-14T12:42:56.830Z
Milos, I don't know other approaches but as you know if you search on Metric Max k-cut, you will find good papers, but if you find good approximation, it's useful assume it as optimum. the error probability is the 1- approximation factor. and with high approximation factor, your error probability will be good.
Saeed
CC BY-SA 2.5
2011-03-14T18:44:12.720Z
note however that the weight function here is SQUARED euclidean distance, which isn't a metric.
Suresh Venkat
CC BY-SA 2.5
2011-03-15T00:48:02.957Z
I would guess that max cut has a ptas, or maybe even a polytime algorithm for these instances, but the specific question is very interesting. Is it clear what is the max cut when the vertices are equally spaced along a cycle, and that the example in this class that minimizes the max cut is three equally spaced vertices? Because there could be an argument that shows that every configuration of points can be converted to a `symmetric' configuration without increasing the ratio of max cut to total weight, and so it might be sufficient to understand only highly symmetric configurations
Luca Trevisan
CC BY-SA 2.5
2011-03-15T00:52:34.120Z
Also, what happens in one dimension? It is possible to find a configuration for which the max cut is approximately 2/3 of the total weight (one point is -1, one point is +1, 4 points are very close to zero; the total weight is 12 and the optimum is 8). Is 2/3 the smallest possible ratio of max cut to total weight in 1 dimension?
Luca Trevisan
CC BY-SA 2.5
2011-03-15T01:54:26.093Z
@Luca: Yes, 1D is also not trivial. Intuitively, the constant should be getting closer to 1/2 as dimension increases. For the 2D case, we might assume that the center of gravity is at (0,0) and that all points fit within the unit circle. There might be some "point repulsion" argument that pushes the points towards the unit circle while not increasing the cut weight, which would help, but I could not pin it down.
Milos Hasan
CC BY-SA 2.5
2011-03-15T02:05:11.510Z
Also, I found that the paper "Polynomial Time Approximation Schemes for Metric Min-Sum Clustering" by de la Vega considers the squared Euclidean case as well. It gives a PTAS, but it does not really illuminate (at least to me) what the optimum should be and why should it get better in low dimension.
Milos Hasan
<ds.algorithms><graph-algorithms><application-of-theory><max-cut><clustering>
Euclidean-squared max-cut in low dimensions
Milos Hasan
# Euclidean-squared max-cut in low dimensions

(Asked by: username_0 on 2011-03-14)

Let $x\_1, \ldots, x\_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x\_i - x\_j\|^2$. Can you always find a cut of weight that is at least $\frac 2 3$ of the total weight? If not, which constant should replace the $\frac 2 3$?

The worst example I'm able to find is 3 points on an equilateral triangle, which achieves the $\frac 2 3$. Note that a random split would produce $\frac 1 2$, but it seems intuitively obvious that in low dimensions, one can cluster better than randomly.

What happens for max-k-cut for k > 2? How about a dimension d > 2? Is there a framework to answer such questions? I know about Cheeger's inequalities, but those apply to sparsest cut (not max-cut) and only work for regular graphs.

(Question is inspired by the problem of clustering light sources in computer graphics to minimize variance).

**Tags:** ds.algorithms, graph-algorithms, application-of-theory, max-cut, clustering

> **Comments:**
> **username_1**: There is a simple 1-2/k approximation for Max k-Cut, and for k>2 you can find a good big cut but for k=2 you can see http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf and related topics, I think if you find a good cut with hi probability you can say there is a cut with 2/3 or not, at least the range of possibility will be limited.  
> **username_0**: username_1, the Goemans-Williamson paper gives an algorithm that finds a cut with a good ratio to the optimum, but what is the ratio of the optimum to the total edge weight? On general graphs, this can be as low as $\frac 1 2$, but if the edge weights are squared distances in low dimensions, can it be higher?  
> **username_1**: Milos, I don't know other approaches but as you know if you search on Metric Max k-cut, you will find good papers, but if you find good approximation, it's useful assume it as optimum. the error probability is the 1- approximation factor. and with high approximation factor, your error probability will be good.  
> **username_2**: note however that the weight function here is SQUARED euclidean distance, which isn't a metric.  
> **username_3**: I would guess that max cut has a ptas, or maybe even a polytime algorithm for these instances, but the specific question is very interesting. Is it clear what is the max cut when the vertices are equally spaced along a cycle, and that the example in this class that minimizes the max cut is three equally spaced vertices? Because there could be an argument that shows that every configuration of points can be converted to a `symmetric' configuration without increasing the ratio of max cut to total weight, and so it might be sufficient to understand only highly symmetric configurations  
> **username_3**: Also, what happens in one dimension? It is possible to find a configuration for which the max cut is approximately 2/3 of the total weight (one point is -1, one point is +1, 4 points are very close to zero; the total weight is 12 and the optimum is 8). Is 2/3 the smallest possible ratio of max cut to total weight in 1 dimension?  
> **username_0**: @Luca: Yes, 1D is also not trivial. Intuitively, the constant should be getting closer to 1/2 as dimension increases. For the 2D case, we might assume that the center of gravity is at (0,0) and that all points fit within the unit circle. There might be some "point repulsion" argument that pushes the points towards the unit circle while not increasing the cut weight, which would help, but I could not pin it down.  
> **username_0**: Also, I found that the paper "Polynomial Time Approximation Schemes for Metric Min-Sum Clustering" by de la Vega considers the squared Euclidean case as well. It gives a PTAS, but it does not really illuminate (at least to me) what the optimum should be and why should it get better in low dimension.  

---

## 2 answers

### Answer by username_3 on 2011-03-15. Score: 7

The constant does tend to 1/2 as the dimension increases. In d dimensions, you can have d+1 points at distance one from each other, so the the sum of distance-squared is ${d+1 \choose 2}$ and the maximum cut is at most $(d+1)^2/4$, which is a $\frac 12 \cdot \frac {d+1}{d}$ fraction of the total weight

> **Comments:**
> **username_0**: OK, but why does the configuration of d+1 points at a distance 1 from each other constitute the worst case? This seems plausible, but is it obvious? (And for d = 1, two points at a distance 1 from each other are clearly not the worst case; the 6-point configuration you gave above is worse. Could it be that d = 1 is the only pathological case, and it works for d >= 2?)  
> **username_2**: @milos I'm not sure I understand. we know that 0.5 is achievable, and this example shows that you can't do better. It doesn't however break the 2/3 conjecture for the plane though.  
> **username_0**: @Suresh: What I was really after is proving that you *can* do better in low dimensions, i.e. I'm interested in the sequence of actual values of the worst constants for particular low d's.  
> **username_0**: I really wanted to prove an actual gap between 1/2 and 2/3 for low d. This would have interesting consequences, i.e. that you can beat Monte Carlo summation/integration (by splitting your problem into sub-problems smartly instead of randomly), if your problem is intrinsically low-dimensional (any many are).  
> **username_3**: Although this is only an answer for large d, it shows what kind of difficulties can come up in the analysis of the small-d case. Suppose that, in 2 dimensions, you could have five points whose pairwise distance-squared are all between 1 and 1.1. Then the total weight is at least 10 and the max cut is at most 6.6. If 2/3 is the right answer for two dimensions, you have to be able to show that if you have five points such that all the pairwise euclidean distances are at least one, one of the pairwise euclidean distances is at least $\sqrt {1.1}$. How do you argue that?  
> **username_0**: There is something about low dimensions that makes it impossible to find many points that are almost equally far from each other, but may indeed be too difficult to get a handle on. Could we instead address the case where $d$ is small but $k$ is large? If you pick $n$ points uniformly within the square $[0,1]^2$, and subdivide the square into $\sqrt{k} \times \sqrt{k}$ bins, then only $\frac{1}{k^2}$ edges will remain uncut on average - much better than the $\frac 1 k$ you'd get by random clustering. When the points are not chosen uniformly at random, can you still cut $1 - \frac{1}{k^2}$?  
> **username_0**: Correction: above should be $\frac{2}{k^2}$ instead of $\frac{1}{k^2}$ - since the largest weight edge that fits into a bin is $\frac 2 k$.  
> **username_3**: it could be that your sets splits into 3 groups, each of k/3 points, and each group is concentrated around one the vertices of a equilateral triangle, giving you the 2/3 bound that you conjecture to be the worst case  
> **username_0**: @Luca: Sorry for some confusion in notation, I'm using $k$ as the number of clusters (as in max-$k$-cut) and $n$ as the number of points. A random partition into $k$ clusters will give you cut weight of $1 - 1/k$, but my binning argument above suggests that $1 - O(k^{-2})$ might be possible in the plane (or more generally $1 - O(k^{-1-2/d})$ in $d$ dimensions.) Does that sound plausible?  
> **username_3**: Oh, I see. That's another very interesting and very difficult question. It would be enough to show that, for any $n$ points for which the average distance-squared is 1 we can find a partition of them into $k$ subsets such that each subset has $O(n/k)$ points, and each subset has euclidean diameter $O(1/\sqrt{k})$. In the special case in which (after the normalization that makes the average distance-squared 1) the points are contained in a disk of radius-squared O(1), it is true  
> **username_3**: Because you can cover the disk of radius $O(1)$ with $O(t)$ squares of euclidean size $1/\sqrt{t} \times 1/\sqrt {t}$ (we'll pick $t$ in a minute), and then you can come up with a partition of the points in the following way: if a square has $\leq 2n/k$ points, then the points in the square are an element of the partition; otherwise, we arbitrarily divide the point in a square into subsets of size $\leq 2n/k$ each. So the number of sets that we end up with is at most $O(t)$ + $n/(2n/k)$ which is at most $O(t)$ + $k/2$ which is at most $k$ for a proper choice of $t=\Theta(k)$  
> **username_0**: Excellent! So if some bins are empty, and others have more than a "fair" share of points, it does not pose a problem. It seems that to prove that the uncut weight is $O(k^{-2})$, you just need to move the points (by affine transformation) into the unit square - no need to worry about normalization of the average weight, since that will only affect the constant in the O() notation.  
> **username_3**: I don't see how you would do it in general. The approach seems to require that the average distance-squared is at least a constant fraction of the maximum distance-squared, which is not true in general.  
> **username_0**: Oh, I see. We need to prove that the uncut weight is $O(k^{-2})$, where the constant is independent of $n$.  

---

### Answer by username_4 on 2011-03-19. Score: 7

Take 3 points A, B, C on an equilateral triangle and add 3 more points D, E, F, in the center. It's clear you want two of A, B, C on one side of the cut, so let's say the cut on these three points is (AB;C). Now, each of the points D, E, F has to go on the C side of the cut, so the optimal cut is (AB; CDEF), and the ratio is easily checked to be 2/3.

Now, move each of the points D, E, F slightly away from the center to form a small equilateral triangle. It doesn't matter in which direction, as long as they're symmetric around the center. If you move them a small enough distance, the optimal cut still has to be (AB; CDEF). Consider the length of this cut. The edges (AC, BC) form 2/3 of the total length of the edges (AB, BC, AC). By symmetry, the total length of the edges (AD, AE, AF, BD, BE, BF) are 2/3 of the length of the edges (AD, AE, AF, BD, BE, BF, CD, CE, CF). But *none* of the edges (DE, EF, DF) are in the cut. So the ratio of this cut is strictly less than 2/3.

You should be able to optimize this construction to find a configuration where the optimal cut is significantly less than 2/3. Trying it, I get that if you take six points arranged in two equilateral triangles having the same center, with the smaller one $(\sqrt{6}-1)/5 \approx .2899$ the size of the larger one, then the max-cut becomes $.6408$ the total weight instead of $2/3$.

> **Comments:**
> **username_0**: Nice, you're right! Well, another elegant conjecture bites the dust... It's still an open question though whether the constant in the plane is larger than 1/2, or whether you can achieve $1 - O(k^{-\alpha})$ with $k$ clusters, where $\alpha > 1$. I'll think about it more.  
> **username_4**: My guess is that the right answer is something not too much lower than .64, but I have no idea how to go about showing a lower bound.  

---

