12
$\begingroup$

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).

Improve this question
$\endgroup$
8
  • $\begingroup$ 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 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. $\endgroup$
    – Saeed
    Mar 14, 2011 at 10:57
  • 1
    $\begingroup$ note however that the weight function here is SQUARED euclidean distance, which isn't a metric. $\endgroup$
    – Suresh Venkat
    Mar 14, 2011 at 18:44
  • 2
    $\begingroup$ 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 $\endgroup$
    – Luca Trevisan
    Mar 15, 2011 at 0:48
  • 2
    $\begingroup$ 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? $\endgroup$
    – Luca Trevisan
    Mar 15, 2011 at 0:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – Milos Hasan
    Mar 15, 2011 at 1:54

2 Answers 2

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
14
  • $\begingroup$ 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?) $\endgroup$
    – Milos Hasan
    Mar 15, 2011 at 8:25
  • 1
    $\begingroup$ @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. $\endgroup$
    – Suresh Venkat
    Mar 15, 2011 at 10:16
  • $\begingroup$ @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. $\endgroup$
    – Milos Hasan
    Mar 15, 2011 at 17:28
  • 1
    $\begingroup$ 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). $\endgroup$
    – Milos Hasan
    Mar 15, 2011 at 17:47
  • 1
    $\begingroup$ 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? $\endgroup$
    – Luca Trevisan
    Mar 15, 2011 at 19:06
7
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Milos Hasan
    Mar 20, 2011 at 22:12
  • $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Mar 20, 2011 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.