Труды Института математики и механики УрО РАН
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды Института математики и механики УрО РАН, 2016, том 22, номер 3, страницы 144–152
DOI: https://doi.org/10.21538/0134-4889-2016-22-3-144-152
(Mi timm1329)
 

Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность

А. В. Кельмановab, Л. В. Михайловаa, С. А. Хамидуллинa, В. И. Хандеевa

a Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
b Новосибирский государственный университет
Список литературы:
Аннотация: Рассматривается задача разбиения конечной последовательности точек евклидова пространства на заданное число кластеров (подпоследовательностей) по критерию минимума суммы по всем кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров задан в начале координат, а центр каждого из остальных кластеров неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер. При этом разбиение подчиненно структурным ограничениям на элементы последовательности, входящие в кластеры с неизвестными центрами: (1) конкатенация номеров элементов этих кластеров является возрастающей последовательностью, (2) разность между последующим и предыдущим номерами ограничена сверху и снизу заданными константами, (3)суммарная мощность кластеров с неизвестными центрами задана на входе. Показано, что задача $NP$-трудна в сильном смысле. Построен 2-приближенный алгоритм, полиномиальный при фиксированном числе кластеров.
Ключевые слова: разбиение, последовательность, евклидово пространство, минимум суммы квадратов расстояний, $NP$-трудность, приближенный алгоритм.
Финансовая поддержка Номер гранта
Российский научный фонд 16-11-10041
Работа выполнена при финансовой поддержке Российского научного фонда (проект 16-11-10041).
Поступила в редакцию: 30.05.2016
Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2017, Volume 299, Issue 1, Pages 88–96
DOI: https://doi.org/10.1134/S0081543817090115
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.16 + 519.85
MSC: 68W25, 68Q25
Образец цитирования: А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность”, Тр. ИММ УрО РАН, 22, № 3, 2016, 144–152; Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96
Цитирование в формате AMSBIB
\RBibitem{KelMikKha16}
\by А.~В.~Кельманов, Л.~В.~Михайлова, С.~А.~Хамидуллин, В.~И.~Хандеев
\paper Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность
\serial Тр. ИММ УрО РАН
\yr 2016
\vol 22
\issue 3
\pages 144--152
\mathnet{http://mi.mathnet.ru/timm1329}
\crossref{https://doi.org/10.21538/0134-4889-2016-22-3-144-152}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3555718}
\elib{https://elibrary.ru/item.asp?id=26530887}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2017
\vol 299
\issue , suppl. 1
\pages 88--96
\crossref{https://doi.org/10.1134/S0081543817090115}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000425144600010}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85042147861}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/timm1329
  • https://www.mathnet.ru/rus/timm/v22/i3/p144
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Труды Института математики и механики УрО РАН
    Статистика просмотров:
    Страница аннотации:289
    PDF полного текста:48
    Список литературы:38
    Первая страница:1
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024