Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
Alexander V. Kel’manov, С. М. Романченко · Automation and Remote Control · 2012
We analyze several NP -hard problems related to clustering and searching, in a given set of vectors in a Euclidean space, for a subset of vectors of fixed size. An important data mining problem related to sum of squares optimization reduces to these problems. We show pseudopolynomial algorithms that are guaranteed to find an optimum in these problems in case when vector components have integer values and the dimension is fixed.