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).
Euclidean-squared max-cut in low dimensions
ds.algorithms;graph algorithms;application of theory;max cut;clustering