|
This article is cited in 16 scientific papers (total in 16 papers)
Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
A. V. Kel'manovab, V. I. Khandeevab a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akademika Koptyuga 4, Novosibirsk, 630090, Russia
b Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia
Abstract:
The strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given sizes (cardinalities) minimizing the sum (over both clusters) of the intracluster sums of squared distances from the elements of the clusters to their centers is considered. It is assumed that the center of one of the sought clusters is specified at the desired (arbitrary) point of space (without loss of generality, at the origin), while the center of the other one is unknown and determined as the mean value over all elements of this cluster. It is shown that unless P = NP, there is no fully polynomial-time approximation scheme for this problem, and such a scheme is substantiated in the case of a fixed space dimension.
Key words:
cluster analysis, partition, Euclidean space, minimum of the sum of squares of distances, NP-hardness, fixed space dimension, FPTAS.
Received: 02.03.2015
Citation:
A. V. Kel'manov, V. I. Khandeev, “Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem”, Zh. Vychisl. Mat. Mat. Fiz., 56:2 (2016), 332–340; Comput. Math. Math. Phys., 56:2 (2016), 334–341
Linking options:
https://www.mathnet.ru/eng/zvmmf10348 https://www.mathnet.ru/eng/zvmmf/v56/i2/p332
|
Statistics & downloads: |
Abstract page: | 296 | Full-text PDF : | 49 | References: | 61 | First page: | 10 |
|