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

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

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



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






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


Ж. вычисл. матем. и матем. физ., 2015, том 55, номер 6, страницы 1076–1085 (Mi zvmmf10227)  

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

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

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

a 630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. СО РАН
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирск. гос. ун-т

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

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

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

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

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2015, 55:6, 1068–1076

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

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

Образец цитирования: А. В. Кельманов, С. А. Хамидуллин, “Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности”, Ж. вычисл. матем. и матем. физ., 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://www.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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf10227
  • http://mi.mathnet.ru/rus/zvmmf/v55/i6/p1076

    ОТПРАВИТЬ: 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. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 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
    2. 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
    3. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры”, Ж. вычисл. матем. и матем. физ., 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
    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 2017, 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
    6. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 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
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:159
    Полный текст:24
    Литература:32
    Первая стр.:9
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020