|
Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность
А. В. Кельмановab, Л. В. Михайловаa, С. А. Хамидуллинa, В. И. Хандеевa a Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
b Новосибирский государственный университет
Аннотация:
Рассматривается задача разбиения конечной последовательности точек евклидова пространства на заданное число кластеров (подпоследовательностей) по критерию минимума суммы по всем кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров задан в начале координат, а центр каждого из остальных кластеров неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер. При этом разбиение подчиненно структурным ограничениям на элементы последовательности, входящие в кластеры с неизвестными центрами: (1) конкатенация номеров элементов этих кластеров является возрастающей последовательностью, (2) разность между последующим и предыдущим номерами ограничена сверху и снизу заданными константами, (3)суммарная мощность кластеров с неизвестными центрами задана на входе. Показано, что задача $NP$-трудна в сильном смысле. Построен 2-приближенный алгоритм, полиномиальный при фиксированном числе кластеров.
Ключевые слова:
разбиение, последовательность, евклидово пространство, минимум суммы квадратов расстояний, $NP$-трудность, приближенный алгоритм.
Поступила в редакцию: 30.05.2016
Образец цитирования:
А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность”, Тр. ИММ УрО РАН, 22, № 3, 2016, 144–152; Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1329 https://www.mathnet.ru/rus/timm/v22/i3/p144
|
Статистика просмотров: |
Страница аннотации: | 293 | PDF полного текста: | 49 | Список литературы: | 38 | Первая страница: | 1 |
|