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

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

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



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






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


Ж. вычисл. матем. и матем. физ., 2018, том 58, номер 12, страницы 2169–2178 (Mi zvmmf10812)  

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

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

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

Аннотация: Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности точек евклидова пространства на два кластера заданных мощностей по критерию минимума суммы по обоим кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Центр одного из кластеров неизвестен и определяется как среднее значение по всем точкам, образующим этот кластер. Центр второго кластера задан в начале координат. При этом разность между номерами последующего и предыдущего элементов последовательности, входящих в первый кластер, ограничена сверху и снизу заданными константами. Предложен рандомизированный алгоритм, который при заданных относительной погрешности и вероятности несрабатывания для установленного значения параметра находит приближëнное решение задачи за полиномиальное время. Найдены условия, при которых алгоритм полиномиален и асимптотически точен. Библ. 19.

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

Финансовая поддержка Номер гранта
Российский научный фонд 16-11-10041
Работа выполнена при финансовой поддержке РНФ (проект №16-11-10041).


DOI: https://doi.org/10.31857/S004446690003560-7

Список литературы: PDF файл   HTML файл

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2018, 58:12, 2078–2085

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

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

Образец цитирования: А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 58:12 (2018), 2169–2178; Comput. Math. Math. Phys., 58:12 (2018), 2078–2085

Цитирование в формате AMSBIB
\RBibitem{KelKhaKha18}
\by А.~В.~Кельманов, С.~А.~Хамидуллин, В.~И.~Хандеев
\paper Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности
\jour Ж. вычисл. матем. и матем. физ.
\yr 2018
\vol 58
\issue 12
\pages 2169--2178
\mathnet{http://mi.mathnet.ru/zvmmf10812}
\crossref{https://doi.org/10.31857/S004446690003560-7}
\elib{https://elibrary.ru/item.asp?id=36759184}
\transl
\jour Comput. Math. Math. Phys.
\yr 2018
\vol 58
\issue 12
\pages 2078--2085
\crossref{https://doi.org/10.1134/S0965542518120138}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000458237300015}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85057742799}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf10812
  • http://mi.mathnet.ru/rus/zvmmf/v58/i12/p2169

    ОТПРАВИТЬ: 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
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:124
    Литература:21
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020