Loading [MathJax]/jax/output/SVG/config.js
Журнал вычислительной математики и математической физики
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

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

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


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




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

Журнал вычислительной математики и математической физики, 2015, том 55, номер 6, страницы 1076–1085
DOI: https://doi.org/10.7868/S0044466915060071 (Mi zvmmf10227) 		 
Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)

Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности

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

a 630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. СО РАН
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирск. гос. ун-т
PDF полного текста (386 kB) Список цитирования (9)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.7868/S0044466915060071
Аннотация: Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности векторов евклидова пространства на два кластера по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Центр первого кластера является оптимизируемой величиной и определяется как среднее значение по всем векторам, образующим этот кластер. Центр второго кластера фиксирован в начале координат. При этом разбиение подчинено условию: разность между номерами последующего и предыдущего векторов, входящих в первый кластер, ограничена сверху и снизу заданными константами. Предложен 2-приближенный полиномиальный алгоритм решения этой задачи. Библ. 14.
Ключевые слова: последовательность евклидовых векторов, кластеризация, минимум суммы квадратов расстояний, NP-трудность, полиномиальный приближенный алгоритм.
Поступила в редакцию: 23.01.2014
Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2015, Volume 55, Issue 6, Pages 1068–1076
DOI: https://doi.org/10.1134/S0965542515060068
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.7
Образец цитирования: А. В. Кельманов, С. А. Хамидуллин, “Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности”, Ж. вычисл. матем. и матем. физ., 55:6 (2015), 1076–1085; Comput. Math. Math. Phys., 55:6 (2015), 1068–1076
Цитирование в формате AMSBIB
\RBibitem{KelKha15}
\by А.~В.~Кельманов, С.~А.~Хамидуллин
\paper Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности
\jour Ж. вычисл. матем. и матем. физ.
\yr 2015
\vol 55
\issue 6
\pages 1076--1085
\mathnet{http://mi.mathnet.ru/zvmmf10227}
\crossref{https://doi.org/10.7868/S0044466915060071}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3358014}
\elib{https://elibrary.ru/item.asp?id=23450665}
\transl
\jour Comput. Math. Math. Phys.
\yr 2015
\vol 55
\issue 6
\pages 1068--1076
\crossref{https://doi.org/10.1134/S0965542515060068}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000356505400013}
\elib{https://elibrary.ru/item.asp?id=23985127}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84934969624}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/zvmmf10227
  • https://www.mathnet.ru/rus/zvmmf/v55/i6/p1076
    • Эта публикация цитируется в следующих 9 статьяx:
    1. Alexander Kel'manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin, Communications in Computer and Information Science, 974, Optimization and Applications, 2019, 131  crossref
    2. А. Р. Айдинян, О. Л. Цветкова, “Алгоритмы кластерного анализа для решения задач с асимметричной мерой близости”, Сиб. журн. вычисл. матем., 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
    3. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 58:12 (2018), 2169–2178  mathnet  crossref  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “A randomized algorithm for a sequence 2-clustering problem”, Comput. Math. Math. Phys., 58:12 (2018), 2078–2085  crossref  isi
    4. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, A. V. Pyatkin, “An Exact Algorithm of Searching for the Largest Cluster in an Integer-Valued Problem of 2-Partitioning a Sequence”, Pattern Recognit. Image Anal., 28:4 (2018), 703  crossref
    5. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры”, Ж. вычисл. матем. и матем. физ., 57:8 (2017), 1392–1400  mathnet  crossref  elib; A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “Approximation algorithm for the problem of partitioning a sequence into clusters”, Comput. Math. Math. Phys., 57:8 (2017), 1376–1383  crossref  isi
    6. 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 2017, IEEE, 2017, 87–90  crossref  isi
    7. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219  crossref
    8. L. I. Rubanov, A. V. Seliverstov, O. A. Zverkov, V. A. Lyubetsky, “A method for identification of highly conserved elements and evolutionary analysis of superphylum Alveolata”, BMC Bioinformatics, 17 (2016), 385  crossref  isi  elib  scopus
    9. Oleg Zverkov, Alexandr Seliverstov, Vassily Lyubetsky, “Regulation of Expression and Evolution of Genes in Plastids of Rhodophytic Branch”, Life, 6:1 (2016), 7  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Статистика просмотров:
    Страница аннотации:275
    PDF полного текста:56
    Список литературы:56
    Первая страница:9
     
      Обратная связь:
    math-net2025_03@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025