# Is n-dimentional assignment problem for points NP-hard?

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.

• 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.
– orlp
Mar 13, 2021 at 18:39
• @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. Mar 13, 2021 at 19:36
• What is the "variance" of a set of $d$-dimensional vectors? Is it the sum of all pairs of squared distances? Mar 14, 2021 at 1:00
• @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. Mar 14, 2021 at 1:29