Аннотация:
Рассматривается задача разбиения конечной последовательности точек евклидова пространства на заданное число кластеров (подпоследовательностей) по критерию минимума суммы по всем кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров задан в начале координат, а центр каждого из остальных кластеров неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер. При этом разбиение подчинено двум структурным ограничениям на номера элементов последовательности, входящих в кластеры с неизвестными центрами: 1) конкатенация номеров элементов этих кластеров является возрастающей последовательностью, 2) разность между последующим и предыдущим номерами ограничена сверху и снизу заданными константами. Показано, что задача NP-трудна в сильном смысле. Построен 2-приближенный алгоритм, полиномиальный при фиксированном числе кластеров. Библ. 8.
Образец цитирования:
А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры”, Ж. вычисл. матем. и матем. физ., 57:8 (2017), 1392–1400; Comput. Math. Math. Phys., 57:8 (2017), 1376–1383
\RBibitem{KelMikKha17}
\by А.~В.~Кельманов, Л.~В.~Михайлова, С.~А.~Хамидуллин, В.~И.~Хандеев
\paper Приближенный алгоритм для задачи разбиения последовательности на кластеры
\jour Ж. вычисл. матем. и матем. физ.
\yr 2017
\vol 57
\issue 8
\pages 1392--1400
\mathnet{http://mi.mathnet.ru/zvmmf10606}
\crossref{https://doi.org/10.7868/S0044466917080087}
\elib{https://elibrary.ru/item.asp?id=29766830}
\transl
\jour Comput. Math. Math. Phys.
\yr 2017
\vol 57
\issue 8
\pages 1376--1383
\crossref{https://doi.org/10.1134/S0965542517080085}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000408956800011}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85028688948}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf10606
https://www.mathnet.ru/rus/zvmmf/v57/i8/p1392
Эта публикация цитируется в следующих 1 статьяx:
Kel'manov A., “Efficient Approximation Algorithms For Some NP-Hard Problems of Partitioning a Set and a Sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 87–90
Цитирование в формате AMSBIB
Обратная связь: