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

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

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



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






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


Сиб. журн. вычисл. матем., 2017, том 20, номер 4, страницы 379–392 (Mi sjvm658)  

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

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

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

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

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

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


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

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

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

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

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

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


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

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