Реферат: We consider two problems that are close in terms of formulation. The first one is that of clustering, i.e., partitioning the set of d-dimensional Euclidean vectors into a given number of clusters with different types of centers so that the total variance would be minimum. Here, by variance we mean the sum of squared distances between the elements of the clusters and their centers. There are three types of centers: an arbitrary point (clearly, the centroid is the best choice), a point of the initial set (the so-called medoid), or a fixed given in advance point in the space. The sizes of the clusters are also given as part of the input. The second problem under consideration is the problem of choosing a subset of vectors of fixed cardinality having the minimum sum of squared distances between its elements and the centroid. Polynomial-time approximation schemes (PTAS) are constructed for each of these problems.

Библиографическая ссылка: Pyatkin A.V.
PTAS for Problems of Vector Choice and Clustering with Various Centers
Journal of Applied and Industrial Mathematics. 2023. V.17. N3. P.600-607. DOI: 10.1134/S1990478923030134 Scopus РИНЦ OpenAlex

Оригинальная: Пяткин А.В.
Полиномиальные апппроксимационные схемы для задач выбора векторов и кластеризации с разными центрами
Дискретный анализ и исследование операций. 2023. Т.30. №3. С.96-110. DOI: 10.33048/daio.2023.30.763 РИНЦ

Даты:

Поступила в редакцию:	7 февр. 2023 г.
Принята к публикации:	25 апр. 2023 г.
Опубликована в печати:	4 нояб. 2023 г.
Опубликована online:	4 нояб. 2023 г.

Идентификаторы БД:

Scopus:	2-s2.0-85175825251
РИНЦ:	63774093
OpenAlex:	W4388337459

Цитирование в БД: Пока нет цитирований

Альметрики: