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

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

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


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




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

Журнал вычислительной математики и математической физики, 2015, том 55, номер 2, страницы 335–344
DOI: https://doi.org/10.7868/S0044466915020131 (Mi zvmmf10162) 		 
Эта публикация цитируется в 28 научных статьях (всего в 28 статьях)

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

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

a 630090 Новосибирск, пр. Ак. Коптюга, 4, Ин-т математики СО РАН
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирск. гос. ун-т
PDF полного текста (240 kB) Список цитирования (28)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.7868/S0044466915020131
Аннотация: Обоснован рандомизированный алгоритм для NP-трудной в сильном смысле задачи разбиения конечного множества векторов евклидова пространства на два кластера заданных размеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из кластеров является оптимизируемой величиной и определяется как среднее значение по всем векторам, образующим этот кластер. Центр другого кластера фиксирован в начале координат. Предложенный алгоритм при заданных относительной ошибке и вероятности несрабатывания для установленного значения параметра находит приближенное решение задачи за линейное от размерности пространства и размера входа задачи время. Найдены условия, при которых алгоритм асимптотически точен и позволяет находить решение за время, линейное от размерности пространства и квадратичное от размера входа задачи. Библ. 23.
Ключевые слова: разбиение, множество векторов, квадраты евклидовых расстояний, NP-трудность, рандомизированный алгоритм, асимптотическая точность.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-00-00462
13-07-00070
Работа выполнена при финансовой поддержке РФФИ (коды проектов 15-00-00462, 13-07-00070).
Поступила в редакцию: 12.03.2014
Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2015, Volume 55, Issue 2, Pages 330–339
DOI: https://doi.org/10.1134/S096554251502013X
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.7
Образец цитирования: А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 55:2 (2015), 335–344; Comput. Math. Math. Phys., 55:2 (2015), 330–339
Цитирование в формате AMSBIB
\RBibitem{KelKha15}
\by А.~В.~Кельманов, В.~И.~Хандеев
\paper Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов
\jour Ж. вычисл. матем. и матем. физ.
\yr 2015
\vol 55
\issue 2
\pages 335--344
\mathnet{http://mi.mathnet.ru/zvmmf10162}
\crossref{https://doi.org/10.7868/S0044466915020131}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3317887}
\elib{https://elibrary.ru/item.asp?id=22908475}
\transl
\jour Comput. Math. Math. Phys.
\yr 2015
\vol 55
\issue 2
\pages 330--339
\crossref{https://doi.org/10.1134/S096554251502013X}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000350801800017}
\elib{https://elibrary.ru/item.asp?id=24011263}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84924119914}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/zvmmf10162
  • https://www.mathnet.ru/rus/zvmmf/v55/i2/p335
    • Эта публикация цитируется в следующих 28 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Статистика просмотров:
    Страница аннотации:340
    PDF полного текста:56
    Список литературы:59
    Первая страница:19
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024