Полиномиальные аппроксимационные схемы для задач выбора векторов и кластеризации с разными центрами
А. В. Пяткин

ЛИТЕРАТУРА
1.	Berkhin P., “A survey of clustering data mining techniques”, Grouping multidimensional data: Recent advances in clustering, Springer, Heidelberg, 2006, 25–71
2.	Jain A. K., Dubes R. C., Algorithms for clustering data, Prentice Hall, Englewood Cliffs, NJ, 1988
3.	Ghoreyshi S., Hosseinkhani J., “Developing a clustering model based on \text{$K$-means} algorithm in order to creating different policies for policyholders”, Int. J. Adv. Comput. Sci. Inf. Tech., 4:2 (2015), 46–53
4.	Fisher W. D., “On grouping for maximum homogeneity”, J. Am. Stat. Assoc., 53:284 (1958), 789–798
5.	MacQueen J., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Mathematics, Statistics and Probability (Berkeley, USA, June 21 — July 18, 1965; Dec. 27, 1965 — Jan. 7, 1966), v. 1, Univ. California Press, Berkeley, 1967, 281–297
6.	Kaufman L., Rousseeuw P. J., “Clustering by means of medoids”, Statistical data analysis based on the $L_1$-norm, North-Holland, Amsterdam, 1987, 405–416
7.	Aloise D., Deshpande A., Hansen P., Popat P., “NP-hardness of Euclidean sum-of-squares clustering”, Mach. Learn., 75:2 (2009), 245–248
8.	Inaba M., Katoh N., Imai H., “Applications of weighted Voronoi diagrams and randomization to variance-based $k$-clustering”, Proc. 10th Annu. Symp. Computational Geometry (Stony Brook, NY, USA, June 6–8, 1994), ACM Press, New York, 1994, 332–339
9.	Kumar A., Sabharwal Y., Sen S., “A simple linear time $(1+\varepsilon)$-approximation algorithm for geometric $k$-means clustering in any dimensions”, Proc. 45th Annu. IEEE Symp. Foundations of Computer Science (Rome, Italy, Oct. 17–19, 2004), IEEE Comp. Soc., Los Alamitos, CA, 2004, 454–462
10.	Бабурин А. Е., Гимади Э. Х., Глебов Н. И., Пяткин А. В., “Задача отыскания подмножества векторов с максимальным суммарным весом”, Дискрет. анализ и исслед. операций. Сер. 2, 14:1 (2007), 32–42      ; A. E. Baburin, É. Kh. Gimadi, N. I. Glebov, and A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Ind. Math., 2:1 (2008), 32–38
11.	Гимади Э. Х., Кельманов А. В., Кельманова М. А., Хамидуллин С. А., “Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов”, Сиб. журн. индустр. математики, 9:1 (2006), 55–74       [É. Kh. Gimadi, A. V. Kel'manov, M. A. Kel'manova, and S. A. Khamidullin, “A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence”, Sib. Zh. Ind. Mat., 9:1 (2006), 55–74]
12.	Кельманов А. В., Пяткин А. В., “О сложности одного из вариантов задачи выбора подмножества «похожих» векторов”, Докл. Акад. наук, 421:5 (2008), 590–592    ; A. V. Kel'manov and A. V. Pyatkin, “On the complexity of a search for a subset of «similar» vectors”, Dokl. Math., 78:1 (2008), 574–575
13.	Кельманов А. В., Пяткин А. В., “Об одном варианте задачи выбора подмножества векторов”, Дискрет. анализ и исслед. операций, 15:5 (2008), 20–34    ; A. V. Kel'manov and A. V. Pyatkin, “On a version of the problem of choosing a vector subset”, J. Appl. Ind. Math., 3:4 (2009), 447–455
14.	Долгушев А. В., Кельманов А. В., “Приближённый алгоритм решения одной задачи кластерного анализа”, Дискрет. анализ и исслед. операций, 18:2 (2011), 29–40      ; A. V. Dolgushev and A. V. Kel'manov, “An approximation algorithm for solving a problem of cluster analysis”, J. Appl. Ind. Math., 5:4 (2011), 551–558
15.	Кельманов А. В., Хандеев В. И., “Полиномиальный алгоритм с оценкой точности 2 для решения одной задачи кластерного анализа”, Дискрет. анализ и исслед. операций, 20:4 (2013), 36–45    ; A. V. Kel'manov and V. I. Khandeev, “A $2$-approximation polynomial algorithm for a clustering problem”, J. Appl. Ind. Math., 7:4 (2013), 515–521
16.	Долгушев А. В., Кельманов А. В., Шенмайер В. В., “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. Ин-та математики и механики, 21:3 (2015), 100–109  ; A. V. Dolgushev, A. V. Kel'manov, and V. V. Shenmaier, “A polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Proc. Steklov Inst. Math., 295, Suppl. 1 (2016), 47–56
17.	Кельманов А. В., Пяткин А. В., Хандеев В. И., “NP-трудность квадратичной евклидовой задачи 2-кластеризации 1-mean и 1-median с ограничениями на размеры кластеров”, Докл. Акад. наук, 489:4 (2019), 339–343    ; A. V. Kel'manov, A. V. Pyatkin, and V. I. Khandeev, “NP-hardness of quadratic Euclidean $1$-mean and $1$-median $2$-clustering problem with constraints on the cluster sizes”, Dokl. Math., 100:3 (2019), 545–548
18.	Pyatkin A. V., “1-Mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation”, Yugoslav J. Oper. Res., 33:1 (2023), 59–69
19.	Шенмайер В. В., “Аппроксимационная схема для одной задачи поиска подмножества векторов”, Дискрет. анализ и исслед. операций, 19:2 (2012), 93–101  ; V. V. Shenmaier, “An approximation scheme for a problem of search for a vector subset”, J. Appl. Ind. Math., 6:3 (2012), 381–386
20.	Галашов А. Е., Кельманов А. В., “2-Приближённый алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов”, Автоматика и телемеханика, 2014, № 4, 5–19      ; A. E. Galashov and A. V. Kel'manov, “A $2$-approximate algorithm to solve one problem of a family of disjoint vector subsets”, Autom. Remote Control, 75:4 (2014), 595–606
21.	Edmonds J., Karp R. M., “Theoretical improvements in algorithmic efficiency for network flow problems”, J. ACM, 19:2 (1972), 248–264
22.	Gabow H. N., Tarjan R. E., “Faster scaling algorithms for network problems”, SIAM J. Comput., 18:5 (1989), 1013–1036
23.	Wirth H., Algorithms + data structures = programs, Prentice Hall, Englewood Cliffs, NJ, 1976