On the complexity of some cluster analysis problems

被引：0

作者：

A. V. Kel’manov

机构：

[1] Russian Academy of Sciences,Sobolev Institute of Mathematics, Siberian Branch

来源：

Computational Mathematics and Mathematical Physics | 2011年 / 51卷

关键词：

discrete optimization; complexity; NP-completeness; clusterization; Euclidean space; data analysis;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

NP-completeness of certain important clusterization problems for a finite set of vectors is proved.

引用

页码：1983 / 1988

页数：5

共 13 条

[1]

Mahajan M.(2009)The Planar k-Means Problem Is NP-Hard Lect. Notes Comput. Sci. 5431 284-285

[2]

Nimbhorkar P.(2011)On the Algorithmic Complexity of a Problem in Cluster Analysis J. Appl. Industr. Math. 5 191-194

[3]

Varadarajan K.(1967)Some Methods for Classification and Analysis of Multivariate Observations Proc. 5th Berkeley Symp. on Mathematical Statistics and Probability 1 281-297

[4]

Dolgushev A. V.(2008)On the Complexity of a Search for a Subset of “Similar” Vectors Dokl. Math. 78 574-575

[5]

Kel’manov A. V.(2009)On a Version of the Problem of Choosing a Vector Subset J. Appl. Industr. Math. 3 447-455

[6]

MacQueen J. B.(2011)“NP-Completeness of Some Problems of Choosing a Vector Subset J. Appl. Industr. Math. 5 352-357

[7]

Kel’manov A. V.(2010)NP-Completeness of Some Searching Vector Subsets Problems Tr. Instituta matematiki i mekhaniki Ural’skogo Otd. RAN 16 121-129

[8]

Pyatkin A. V.(undefined)undefined undefined undefined undefined-undefined

[9]

Kel’manov A. V.(undefined)undefined undefined undefined undefined-undefined

[10]

Pyatkin A. V.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →