Geodesic
Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 100-109 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider the strongly $NP$-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given cardinalities under the minimum criterion for the sum over the clusters of the intracluster sums of squared distances from elements of the cluster to its center. It is assumed that the center of one of the clusters is given (without loss of generality, at the origin). The center of the second cluster is unknown and is determined as the mean value over all elements in this cluster. A polynomial-time approximation scheme (PTAS) is provided.
Keywords: ptas, cluster analysis, euclidean space, $np$-hard problem, ptas. 
@article{TIMM_2015_21_3_a10,
     author = {A. V. Dolgushev and A. V. Kel'manov and V. V. Shenmaier},
     title = {Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {100--109},
     year = {2015},
     volume = {21},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a10/}
}
TY  - JOUR
AU  - A. V. Dolgushev
AU  - A. V. Kel'manov
AU  - V. V. Shenmaier
TI  - Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2015
SP  - 100
EP  - 109
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a10/
LA  - ru
ID  - TIMM_2015_21_3_a10
ER  - 
%0 Journal Article
%A A. V. Dolgushev
%A A. V. Kel'manov
%A V. V. Shenmaier
%T Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
%J Trudy Instituta matematiki i mehaniki
%D 2015
%P 100-109
%V 21
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a10/
%G ru
%F TIMM_2015_21_3_a10
A. V. Dolgushev; A. V. Kel'manov; V. V. Shenmaier. Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 100-109. http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a10/

[1] D. Aloise, A. Deshpande, P. Hansen, P. Popat, “$NP$-hardness of Euclidean sum-of-squares clustering”, Machine Learning, 75:2 (2009), 245–248 | DOI

[2] Anil K., Jain K., “Data clustering: 50 years beyond $k$-means”, Pattern Recognition Letters, 31 (2010), 651–666 | DOI

[3] Garey M.R., Johnson D.S., Computers and intractability: a guide to the theory of $NP$-completeness, Freeman, San Francisco, 1979, 314 pp. | MR | Zbl

[4] E.Kh. Gimadi, A.V. Kel'manov, M.A. Kel'manova, S.A. Khamidullin, “A posteriori detecting a quasiperiodic fragment in a numerical sequence”, Pattern Recognition and Image Analysis, 18:1 (2008), 30–42 | DOI | MR

[5] Kel'manov A., Khandeev V., “An exact pseudopolynomial algorithm for a bi-partitioning problem”, Optimization and Applications — OPTIMA-2014, Proc. V Intern. Conf. (Petrovac, Montenegro, September 28 – October 4), Dorodnicyn Computing Centre of RAS, Moscow, 2014, 108–109

[6] Wirth N., Algorithms + Data Structures = Programs, Prentice-Hall Series in Automatic Computation, Prentice Hall, New Jersey, 1976, 366 pp. | MR | Zbl

[7] A.E. Baburin, E.Kh. Gimadi, N.I. Glebov, A.V. Pyatkin, “Zadacha otyskaniya podmnozhestva vektorov s maksimalnym summarnym vesom”, Diskret. analiz i issled. oper., 14:1 (2007), 32–42 | MR | Zbl

[8] Gimadi E.Kh., Glazkov Yu.V., Rykov I.A., “O dvukh zadachakh vybora podmnozhestva vektorov s tselochislennymi koordinatami v evklidovom prostranstve s maksimalnoi normoi summy razmernosti”, Diskret. analiz i issled. oper., 15:4 (2008), 30–43 | MR | Zbl

[9] E.Kh. Gimadi, A.V. Kelmanov, M.A. Kelmanova, S.A. Khamidullin, “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov”, Sib. zhurn. industr. matematiki, 9:1(25) (2006), 55–74 | MR | Zbl

[10] Gimadi E.Kh., Pyatkin A.V., Rykov I.A., “O polinomialnoi razreshimosti nekotorykh zadach vybora podmnozhestv vektorov v evklidovom prostranstve fiksirovannoi razmernosti”, Diskret. analiz i issled. oper., 15:6 (2008), 11–19 | MR | Zbl

[11] Dolgushev A.V., Kelmanov A.V., “Priblizhennyi algoritm resheniya odnoi zadachi klasternogo analiza”, Diskret. analiz i issledovanie operatsii, 18:2 (2011), 29–40 | Zbl

[12] Kelmanov A.V., “O slozhnosti nekotorykh zadach analiza dannykh”, Zhurn. vychisl. matematiki i mat. fiziki, 50:11 (2010), 2045–2051 | MR | Zbl

[13] Kelmanov A.V., “O slozhnosti nekotorykh zadach klasternogo analiza”, Zhurn. vychisl. matematiki i mat. fiziki, 51:11 (2011), 2106–2112 | MR | Zbl

[14] Kelmanov A.V., Pyatkin A.V., “O slozhnosti odnogo iz variantov zadachi vybora podmnozhestva “pokhozhikh” vektorov”, Dokl. AN, 421:5 (2008), 590–592 | Zbl

[15] Kelmanov A.V., Pyatkin A.V., “Ob odnom variante zadachi vybora podmnozhestva vektorov”, Diskret. analiz i issled. oper., 15:5 (2008), 20–34 | MR | Zbl

[16] Kelmanov A.V., Pyatkin A.V., “O slozhnosti nekotorykh zadach poiska podmnozhestv vektorov i klasternogo analiza”, Zhurn. vychisl. matematiki i mat. fiziki, 49:11 (2009), 2059–2067 | MR

[17] Kelmanov A.V., Khandeev V.I., “FPTAS dlya odnoi zadachi dvukhklasternogo razbieniya mnozhestva vektorov”, Matematicheskoe programmirovanie i prilozheniya, tez. dokl. XV Vseros. konf. (In-t matematiki i mekhaniki UrO RAN. Ekaterinburg), 2015, 141

[18] Kelmanov A.V., Khandeev V.I., “Randomizirovannyi algoritm dlya odnoi zadachi dvukhklasternogo razbieniya mnozhestva vektorov”, Zhurn. vychisl. matematiki i mat. fiziki, 55:2 (2015), 335–344 | DOI | MR | Zbl

[19] Shenmaier V.V., “Approksimatsionnaya skhema dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskret. analiz i issled. oper., 19:2 (2012), 92–100 | MR | Zbl