1
$\begingroup$

We have $n$ sets of $k$ points in $\mathbb R^d$ and we are trying to partition them to $k$ clusters of $n$ points such that from each set every point is mapped to a different cluster and the sum of variances of each cluster is minimized, i.e., we are trying to solve the $k$-means problem but with the constraint that points from the same set can't go to the same cluster.

I know that even for $n=3,d=2$ this problem is NP-hard in $k$ but I'm trying to figure out if for constant $k$ this problem is NP-hard in $n$?

I've looked in the Wikipedia page of NP-hard problems and tried to think if I can do a reduction to one of them but i couldn't think of any way to do so.

Improve this question
$\endgroup$
4
  • $\begingroup$ I don't know about NP-hardness in the worst case but I would expect great practical results from stress-minimization approaches where two points have a very large stress coefficient if they are from the same set and close. $\endgroup$
    – orlp
    Mar 13, 2021 at 18:39
  • $\begingroup$ @orlp for constant k I proved a way to get a (1+epsilon)-approximation in time O(nd)+2^O(1/epsilon^2), and for larger k I proved a 2-approximation in time O(n(dk^2+k^3)) and for small constant values of d there are ways to make this algorithm O(nk^2). And we can always run EM to hueristically improve a solution untill we get a very good solution, so I already have practical ways to solve this but now I care more about the theoretical side of whether or not it's NP hard to know if it's even possible to get a better proven result then mine in polynomial time. $\endgroup$
    – Tomer Wolberg
    Mar 13, 2021 at 19:36
  • $\begingroup$ What is the "variance" of a set of $d$-dimensional vectors? Is it the sum of all pairs of squared distances? $\endgroup$
    – j_random_hacker
    Mar 14, 2021 at 1:00
  • $\begingroup$ @j_random_hacker it is the sum of squared distances to the mean divided by n. This also equals the sum of squared distances between any 2 points in the cluster divided by n^2. $\endgroup$
    – Tomer Wolberg
    Mar 14, 2021 at 1:29

0

Reset to default

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.