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.

  • $\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$ 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$ 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$ Mar 14, 2021 at 1:29


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.