Given K sets of points, choose one point from each set such that the sum of pairwise distances between the selected points is minimized

Question

Very similar to this question

Selecting an integer from each of the given n sets of integers such that the sum of their pairwise distances is minimized

except instead of integers we have multidimensional feature vectors with an arbitrary distance function for measuring their similarity.

The person who posted that question claimed that they had found a polynomial time solution to their problem that would appear to also work for my problem, but I couldn't understand their answer and it wasn't clear if it was actually correct.

My problem is also equivalent to this question with the weights of the graph equal to the similarity function's outputs.

max-weight k-clique in a complete k-partite graph

But it's unclear if the k-partiteness makes this problem any easier than the general max-weight clique problem.

edit:

From David Eisenstat's answer, it looks the original question isn't solvable in polynomial time. But does anything change if the objective is minimize the maximum pairwise distance between the selected points?

Answer 1

The other answer must be using the particular properties of the integers, because this version is NP-hard. Given k and an undirected graph G = (V, E), we can detect whether G has a k-clique by letting there be points V × {1, …, n} and setting d((v, i), (w, j)) = 1 if {v, w} ∈ E and i ≠ j, with d((v, i), (w, j)) = 2 otherwise. Each set consists of the points V × {i} for some i.

Evgeny Kluev's local search algorithm may be a reasonable thing to try. Initialize a solution with random points, then do the following repeatedly. For some random set (or collection of sets), determine the optimal solution subject to the constraint that the points from other sets stay the same. Retry the whole computation a few times to avoid local minima.