My problem is:

Given $n$ points in $\mathbb{R}^d$, I want to find a partition of these $n$ points into $k=2$ clusters. For each cluster, instead of computing the centroid as in the usual k-means problem, I construct the one-dimensional subspace (what I call a line) minimizing the sum of squared distances between the points of the cluster and the line. So, overall, I want to find a partition such that the total sum of the squared distances between each point and the best line going through its cluster is minimized.

For the usual k-means problem, I know that there exists a polynomial algorithm when $d$ and $k$ are fixed, and is NP-hard when one of the two is part of the input.

Related to this problem, after asking this question on cs.stackexchange (a particular case when $d=2$), I came across this question on stackoverflow where we can read this sentence in the validated answer:

it's well known that finding a globally optimal fit for even two lines to an arbitrary set of points is NP-Hard as it can be reduced to k-means clustering

My question concerns the quote above: Does anyone know a reference to this reduction claimed to be well-known?

After lots of research and attempts to build it myself, I am not able to find such a reduction.

  • 1
    $\begingroup$ Could you please make the question self contained. What is the objective function you are trying to minimize. $\endgroup$ Commented Jul 2, 2023 at 20:11
  • $\begingroup$ I suggest you start by doing some research to understand the claims about NP-hardness of k-means clustering, e.g., cs.stackexchange.com/q/153074/755, stats.stackexchange.com/q/396965/2921, stackoverflow.com/q/18634149/781723, then try to formulate your problem in a self-contained and precise/mathematical way (what is the objective function you are trying to minimize?), then try to come up with such a reduction. $\endgroup$
    – D.W.
    Commented Jul 2, 2023 at 22:21
  • $\begingroup$ @InuyashaYagami The objective function is the sum of the squared distances. $\endgroup$
    – T. Pmp
    Commented Jul 2, 2023 at 22:56
  • $\begingroup$ @D.W. I clarified my problem but my question is more about the quote claiming the reduction is well-known although I did not find any trace of it. $\endgroup$
    – T. Pmp
    Commented Jul 2, 2023 at 22:58
  • $\begingroup$ I don't know how to build such a reduction other, and I too am questioning whether one exists. But perhaps understanding how k-means clustering was proven NP-hard would give some ideas for reduction strategies to prove your problem NP-hard (even if it doesn't have a direct reduction from k-means clustering). $\endgroup$
    – D.W.
    Commented Jul 2, 2023 at 23:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.