Abstract: Рассматриваются две близкие в постановочном плане задачи. Во-первых, общая задача кластеризации, т. е. разбиения множества d-мерных евклидовых векторов на заданное число кластеров с разными типами центров, при котором суммарная дисперсия будет минимальной. Под дисперсией понимается сумма квадратов расстояний между элементами кластера и его центром. При этом для одной части кластеров центр может быть выбран произвольно (очевидно, что в этом случае следует выбрать центроид), для другой части в качестве центра должен быть выбран один из векторов исходного множества, а для остальных кластеров центрами являются заранее заданные точки. Также на входе задаются размеры каждого кластера. Вторая рассматриваемая задача это задача выбора подмножества векторов заданной мощности с минимальной суммой квадратов расстояний от его элементов до центроида. В статье построены полиномиальные аппроксимационные схемы (PTAS) для обеих задач.

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

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

Dates:

Submitted:	Feb 7, 2023
Accepted:	Apr 25, 2023
Published print:	Oct 20, 2023
Published online:	Oct 20, 2023

Identifiers:

Elibrary:

55049251

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

Altmetrics: