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

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

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


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




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

Сибирский журнал вычислительной математики, 2017, том 20, номер 1, страницы 15–22
DOI: https://doi.org/10.15372/SJNM20170102 (Mi sjvm632) 		 
Эта публикация цитируется в 1 научной статье (всего в 1 статье)

О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств

А. Е. Галашовa, А. В. Кельмановab

a Новосибирский национальный исследовательский государственный университет (НГУ), ул. Пирогова, 2, Новосибирск, 630090
b Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, просп. Акад. В. А. Коптюга, 4, Новосибирск, 630090
PDF полного текста (419 kB) Список цитирования (1)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.15372/SJNM20170102
Аннотация: Рассматривается NP-трудная в сильном смысле задача поиска в конечном множестве точек евклидова пространства семейства непересекающихся подмножеств, имеющих заданные мощности. Критерием решения задачи является минимум суммы по всем подмножествам сумм квадратов расстояний от элементов подмножеств до их геометрических центров. Доказано, что задача разрешима за псевдополиномиальное время, если координаты входных точек целочисленны, а размерность пространства и число искомых подмножеств фиксированы (ограничены константами).
Ключевые слова: поиск подмножеств, кластерный анализ, евклидово пространство, минимум суммы квадратов расстояний, NP-трудная задача, точный псевдополинимиальный алгоритм.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-01-00462
16-07-00168
Работа выполнена при поддержке РФФИ (проекты № 15-01-00462, № 16-07-00168).
Статья поступила: 26.07.2016
Переработанный вариант: 29.08.2016
Англоязычная версия:
Numerical Analysis and Applications, 2017, Volume 10, Issue 1, Pages 11–16
DOI: https://doi.org/10.1134/S1995423917010025
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.2+621.391
Образец цитирования: А. Е. Галашов, А. В. Кельманов, “О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств”, Сиб. журн. вычисл. матем., 20:1 (2017), 15–22; Num. Anal. Appl., 10:1 (2017), 11–16
Цитирование в формате AMSBIB
\RBibitem{GalKel17}
\by А.~Е.~Галашов, А.~В.~Кельманов
\paper О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств
\jour Сиб. журн. вычисл. матем.
\yr 2017
\vol 20
\issue 1
\pages 15--22
\mathnet{http://mi.mathnet.ru/sjvm632}
\crossref{https://doi.org/10.15372/SJNM20170102}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3629065}
\elib{https://elibrary.ru/item.asp?id=28400342}
\transl
\jour Num. Anal. Appl.
\yr 2017
\vol 10
\issue 1
\pages 11--16
\crossref{https://doi.org/10.1134/S1995423917010025}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000396367300002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85014770273}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/sjvm632
  • https://www.mathnet.ru/rus/sjvm/v20/i1/p15
    • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Сибирский журнал вычислительной математики
    Статистика просмотров:
    Страница аннотации:192
    PDF полного текста:44
    Список литературы:34
    Первая страница:15
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024