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

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

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



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






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


Ж. вычисл. матем. и матем. физ., 2013, том 53, номер 1, страницы 143–153 (Mi zvmmf9800)  

Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов

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

630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. им. С. Л. Соболева Сибирск. отделения РАН

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

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

DOI: https://doi.org/10.7868/S0044466913010055

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

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

Тип публикации: Статья
УДК: 519.7
Поступила в редакцию: 13.02.2012

Образец цитирования: А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Ж. вычисл. матем. и матем. физ., 53:1 (2013), 143–153

Цитирование в формате AMSBIB
\RBibitem{KelRomKha13}
\by А.~В.~Кельманов, С.~М.~Романченко, С.~А.~Хамидуллин
\paper Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов
\jour Ж. вычисл. матем. и матем. физ.
\yr 2013
\vol 53
\issue 1
\pages 143--153
\mathnet{http://mi.mathnet.ru/zvmmf9800}
\crossref{https://doi.org/10.7868/S0044466913010055}
\elib{http://elibrary.ru/item.asp?id=18446753}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf9800
  • http://mi.mathnet.ru/rus/zvmmf/v53/i1/p143

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 55:2 (2015), 335–344  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339  crossref  isi  elib
    2. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502  crossref
    3. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Аппроксимационная схема для задачи поиска подпоследовательности”, Сиб. журн. вычисл. матем., 20:4 (2017), 379–392  mathnet  crossref  elib; A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “An approximation scheme for a problem of finding a subsequence”, Num. Anal. Appl., 10:4 (2017), 313–323  crossref  isi
    4. A. Kel'manov, “Efficient approximation algorithms for some NP-hard problems of partitioning a set and a sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences, SIBIRCON, IEEE, 2017, 87–90  crossref  isi
    5. А. Р. Айдинян, О. Л. Цветкова, “Алгоритмы кластерного анализа для решения задач с асимметричной мерой близости”, Сиб. журн. вычисл. матем., 21:2 (2018), 127–138  mathnet  crossref  elib; A. R. Aydinyan, O. L. Tsvetkova, “The cluster algorithms for solving problems with asymmetric proximity measures”, Num. Anal. Appl., 11:2 (2018), 99–107  crossref  isi  elib
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:262
    Полный текст:63
    Литература:52
    Первая стр.:13
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019