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

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

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


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




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

Сибирский журнал вычислительной математики, 2017, том 20, номер 4, страницы 379–392
DOI: https://doi.org/10.15372/SJNM20170403 (Mi sjvm658) 		 
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

Аппроксимационная схема для задачи поиска подпоследовательности

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

a Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, просп. Акад. В. А. Коптюга, 4, Новосибирск, 630090
b Новосибирский национальный исследовательский государственный университет, ул. Пирогова, 2, Новосибирск, 630090
PDF полного текста (550 kB) Список цитирования (5)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.15372/SJNM20170403
Аннотация: Рассматривается NP-трудная в сильном смысле задача поиска подпоследовательности с заданным числом элементов в конечной последовательности точек евклидова пространства. Критерием решения является минимум суммы квадратов расстояний от элементов искомой подпоследовательности до их геометрического центра. Выбор элементов подпоследовательности подчинен условию: разность между номерами последующего и предыдущего искомых элементов ограничена сверху и снизу заданными константами. Предложен приближенный алгоритм решения задачи. Доказано, что он является полностью полиномиальной аппроксимационной схемой (FPTAS), если размерность пространства ограничена константой.
Ключевые слова: последовательность, евклидово пространство, минимум суммы квадратов расстояний, NP-трудность, FPTAS.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-01-00462
16-31-00186-мол-а
16-07-00168
Работа выполнена при финансовой поддержке РФФИ (проекты № 15-01-00462, № 16-31-00186-мол-а, № 16-07-00168).
Статья поступила: 01.09.2016
Переработанный вариант: 08.01.2017
Англоязычная версия:
Numerical Analysis and Applications, 2017, Volume 10, Issue 4, Pages 313–323
DOI: https://doi.org/10.1134/S1995423917040036
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.2+621.391
Образец цитирования: А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Аппроксимационная схема для задачи поиска подпоследовательности”, Сиб. журн. вычисл. матем., 20:4 (2017), 379–392; Num. Anal. Appl., 10:4 (2017), 313–323
Цитирование в формате AMSBIB
\RBibitem{KelRomKha17}
\by А.~В.~Кельманов, С.~М.~Романченко, С.~А.~Хамидуллин
\paper Аппроксимационная схема для задачи поиска подпоследовательности
\jour Сиб. журн. вычисл. матем.
\yr 2017
\vol 20
\issue 4
\pages 379--392
\mathnet{http://mi.mathnet.ru/sjvm658}
\crossref{https://doi.org/10.15372/SJNM20170403}
\elib{https://elibrary.ru/item.asp?id=30564536}
\transl
\jour Num. Anal. Appl.
\yr 2017
\vol 10
\issue 4
\pages 313--323
\crossref{https://doi.org/10.1134/S1995423917040036}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000426352400003}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85042695119}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/sjvm658
  • https://www.mathnet.ru/rus/sjvm/v20/i4/p379
    • Эта публикация цитируется в следующих 5 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Сибирский журнал вычислительной математики
    Статистика просмотров:
    Страница аннотации:177
    PDF полного текста:23
    Список литературы:32
    Первая страница:12
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024