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

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

Переводная: 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

Даты:

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

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

РИНЦ:

55049251

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

Альметрики: