|
Avtomatika i Telemekhanika, 2012, Issue 2, Pages 156–162
(Mi at3618)
|
|
|
|
This article is cited in 21 scientific papers (total in 21 papers)
Integer Programming Problems
Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
A. V. Kel'manova, S. M. Romanchenkob a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
Abstract:
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.
Citation:
A. V. Kel'manov, S. M. Romanchenko, “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems”, Avtomat. i Telemekh., 2012, no. 2, 156–162; Autom. Remote Control, 73:2 (2012), 349–354
Linking options:
https://www.mathnet.ru/eng/at3618 https://www.mathnet.ru/eng/at/y2012/i2/p156
|
Statistics & downloads: |
Abstract page: | 396 | Full-text PDF : | 75 | References: | 53 | First page: | 12 |
|