Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems

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.

Presented by the member of Editorial Board: A. I. Kibzun