NP-hardness of Euclidean sum-of-squares clustering Page 1 Mach Learn (2009) 75: 245–248
DOI 10.1007/s10994-009-5103-0 NP-hardness of Euclidean sum-of-squares clustering Daniel …

∑ K Complexity of Certain Problems of Searching for Subsets of Vectors and Cluster Analysis
Page 1 ISSN 0965 5425, Computational Mathematics and Mathematical Physics, 2009, Vol. 49 …

The NP-completeness is proved of the problem of choosing some subset of “similar” vectors.
One of the variants of the a posteriori (off-line) noise-proof detection problem of an unknown …

NP-completeness of two clustering (partition) problems is proved for a finite sequence of
Euclidean vectors. In the optimization versions of both problems it is required to partition the …

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 …

A 2-approximation algorithm is presented for some NP-hard data analysis problem that
consists in partitioning a set of Euclidean vectors into two subsets (clusters) under the …

Доказана NP-полнота двух задач кластеризации (разбиения) конечной
последовательности векторов евклидова пространства. В оптимизационных вариантах …

This note presents a generic approach to proving NP-hardness of unconstrained partition
type problems, namely partitioning a given set of entities into several subsets such that a …

Given an undirected graph G=(V, E), the (uniform, unweighted) sparsest cut problem is to
find a vertex subset S⊂ V minimizing| E (S, S¯)|/(| S|| S¯|). We show that this problem is NP …

We prove that the MSSC problem (the problem of clustering the set of the vectors in the
Euclidean space which minimizes the sum of squares) is NP-complete in the case when the …