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

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

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



Ж. вычисл. матем. и матем. физ.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Ж. вычисл. матем. и матем. физ., 2017, том 57, номер 8, страницы 1392–1400 (Mi zvmmf10606)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

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

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

a 630090 Новосибирск, пр-т акад. Коптюга, 4, Ин-т матем. СО РАН
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирский гос. ун-т

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

Ключевые слова: разбиение, последовательность, евклидово пространство, минимум суммы квадратов расстояний, NP-трудность, приближенный алгоритм.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-01-00462_а
16-31-00186_мол_а
16-07-00168_а
Работа выполнена при финансовой поддержке РФФИ (коды проектов 15-01-00462, 16-31-00186-мол-а и 16-07-00168).


DOI: https://doi.org/10.7868/S0044466917080087

Полный текст: PDF файл (212 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2017, 57:8, 1376–1383

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.7
Поступила в редакцию: 29.02.2016

Образец цитирования: А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры”, Ж. вычисл. матем. и матем. физ., 57:8 (2017), 1392–1400; Comput. Math. Math. Phys., 57:8 (2017), 1376–1383

Цитирование в формате AMSBIB
\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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000408956800011}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85028688948}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf10606
  • http://mi.mathnet.ru/rus/zvmmf/v57/i8/p1392

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. 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  crossref  isi
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:105
    Полный текст:2
    Литература:18
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020