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

Cite: Кельманов А.В. , Михайлова Л.В. , Хамидуллин С.А. , Хандеев В.И.
ПРИБЛИЖЕННЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ РАЗБИЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ НА КЛАСТЕРЫ
Журнал вычислительной математики и математической физики. 2017. Т.57. №8. С.1392-1400. DOI: 10.7868/s0044466917080087 РИНЦ OpenAlex

Translated: Kel’manov A.V. , Mikhailova L.V. , Khamidullin S.A. , Khandeev V.I.
Approximation algorithm for the problem of partitioning a sequence into clusters
Computational Mathematics and Mathematical Physics. 2017. V.57. N8. P.1376-1383. DOI: 10.1134/s0965542517080085 WOS Scopus OpenAlex

Identifiers:

Elibrary:	29766830
OpenAlex:	W2789658991

Citing:

DB	Citing
Elibrary	1

Altmetrics: