Abstract: 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.

Cite: 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

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

Dates:

Submitted:	Feb 7, 2023
Accepted:	Apr 25, 2023
Published print:	Nov 4, 2023
Published online:	Nov 4, 2023

Identifiers:

Scopus:	2-s2.0-85175825251
Elibrary:	63774093
OpenAlex:	W4388337459

Citing: Пока нет цитирований

Altmetrics: