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

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

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



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






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


Сиб. журн. вычисл. матем., 2017, том 20, номер 1, страницы 15–22 (Mi sjvm632)  

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

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

a Новосибирский национальный исследовательский государственный университет (НГУ), ул. Пирогова, 2, Новосибирск, 630090
b Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, просп. Акад. В. А. Коптюга, 4, Новосибирск, 630090

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

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

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


DOI: https://doi.org/10.15372/SJNM20170102

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

Англоязычная версия:
Numerical Analysis and Applications, 2017, 10:1, 11–16

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

Тип публикации: Статья
УДК: 519.2+621.391
Статья поступила: 26.07.2016
Переработанный вариант: 29.08.2016

Образец цитирования: А. Е. Галашов, А. В. Кельманов, “О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств”, Сиб. журн. вычисл. матем., 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://www.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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000396367300002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85014770273}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/sjvm632
  • http://mi.mathnet.ru/rus/sjvm/v20/i1/p15

    ОТПРАВИТЬ: 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
  • Сибирский журнал вычислительной математики
    Просмотров:
    Эта страница:123
    Полный текст:14
    Литература:19
    Первая стр.:15
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020