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

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

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



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






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


Ж. вычисл. матем. и матем. физ., 2009, том 49, номер 11, страницы 2059–2065 (Mi zvmmf4789)  

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

О сложности некоторых задач поиска подмножеств векторов и кластерного анализа

А. В. Кельманов, А. В. Пяткин

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

Аннотация: Доказана NP-полнота дискретных экстремальных задач, к которым сводятся некоторые варианты проблемы поиска подмножеств векторов и кластерного анализа. Библ. 16.

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

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

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2009, 49:11, 1966–1971

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

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

Образец цитирования: А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач поиска подмножеств векторов и кластерного анализа”, Ж. вычисл. матем. и матем. физ., 49:11 (2009), 2059–2065; Comput. Math. Math. Phys., 49:11 (2009), 1966–1971

Цитирование в формате AMSBIB
\RBibitem{KelPya09}
\by А.~В.~Кельманов, А.~В.~Пяткин
\paper О~сложности некоторых задач поиска подмножеств векторов и кластерного анализа
\jour Ж. вычисл. матем. и матем. физ.
\yr 2009
\vol 49
\issue 11
\pages 2059--2065
\mathnet{http://mi.mathnet.ru/zvmmf4789}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2677194}
\transl
\jour Comput. Math. Math. Phys.
\yr 2009
\vol 49
\issue 11
\pages 1966--1971
\crossref{https://doi.org/10.1134/S0965542509110128}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000272464100012}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-71549157161}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf4789
  • http://mi.mathnet.ru/rus/zvmmf/v49/i11/p2059

    ОТПРАВИТЬ: 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. А. В. Долгушев, А. В. Кельманов, “К вопросу об алгоритмической сложности одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 17:2 (2010), 39–45  mathnet  mathscinet  zmath
    2. А. В. Кельманов, А. В. Пяткин, “NP-полнота некоторых задач выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 17:5 (2010), 37–45  mathnet  mathscinet  zmath; A. V. Kel'manov, A. V. Pyatkin, “NP-completeness of some problems of a vectors subset choice”, J. Appl. Industr. Math., 5:3 (2011), 352–357  crossref
    3. А. В. Кельманов, “$NP$-полнота некоторых задач поиска подмножеств векторов”, Тр. ИММ УрО РАН, 16, № 3, 2010, 121–129  mathnet  elib
    4. А. В. Кельманов, “О сложности некоторых задач анализа данных”, Ж. вычисл. матем. и матем. физ., 50:11 (2010), 2045–2051  mathnet  adsnasa; A. V. Kel'manov, “On the complexity of some data analysis problems”, Comput. Math. Math. Phys., 50:11 (2010), 1941–1947  crossref  isi
    5. А. В. Кельманов, “О сложности некоторых задач кластерного анализа”, Ж. вычисл. матем. и матем. физ., 51:11 (2011), 2106–2112  mathnet  mathscinet; A. V. Kel'manov, “On the complexity of some cluster analysis problems”, Comput. Math. Math. Phys., 51:11 (2011), 1983–1988  crossref  isi
    6. А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач кластерного анализа векторных последовательностей”, Дискретн. анализ и исслед. опер., 20:2 (2013), 47–57  mathnet  mathscinet; A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some vector sequence clustering problems”, J. Appl. Industr. Math., 7:3 (2013), 363–369  crossref
    7. А. В. Кельманов, В. И. Хандеев, “Полиномиальный алгоритм с оценкой точности $2$ для решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 20:4 (2013), 36–45  mathnet  mathscinet; A. V. Kelmanov, V. I. Khandeev, “A $2$-approximation polynomial algorithm for one clustering problem”, J. Appl. Industr. Math., 7:4 (2013), 515–521  crossref
    8. А. В. Кельманов, С. А. Хамидуллин, “Приближённый полиномиальный алгоритм для одной задачи разбиения последовательности”, Дискретн. анализ и исслед. опер., 21:1 (2014), 53–66  mathnet  mathscinet; A. V. Kelmanov, S. A. Khamidullin, “Approximation algorithm for one problem of partitioning a sequence”, J. Appl. Industr. Math., 8:2 (2014), 236–244  crossref
    9. А. В. Кельманов, С. А. Хамидуллин, “Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности”, Ж. вычисл. матем. и матем. физ., 55:6 (2015), 1076–1085  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, S. A. Khamidullin, “An approximation polynomial-time algorithm for a sequence bi-clustering problem”, Comput. Math. Math. Phys., 55:6 (2015), 1068–1076  crossref  isi  elib
    10. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 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
    11. А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 21, № 3, 2015, 100–109  mathnet  mathscinet  elib; A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 47–56  crossref  isi
    12. А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 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
    13. Kel'manov A.V. Pyatkin A.V., “NP-Hardness of Some Quadratic Euclidean 2-Clustering Problems”, Dokl. Math., 92:2 (2015), 634–637  crossref  mathscinet  zmath  isi  scopus
    14. А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:2 (2016), 332–340  mathnet  crossref  elib; A. V. Kel'manov, V. I. Khandeev, “Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem”, Comput. Math. Math. Phys., 56:2 (2016), 334–341  crossref  isi
    15. А. В. Кельманов, А. В. Пяткин, “О сложности некоторых квадратичных евклидовых задач 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:3 (2016), 498–504  mathnet  crossref  elib; A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some quadratic Euclidean 2-clustering problems”, Comput. Math. Math. Phys., 56:3 (2016), 491–497
    16. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 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
    17. Kel'manov A.V., Pyatkin A.V., “On the complexity of some Euclidean problems of partitioning a finite set of points”, Dokl. Math., 94:3 (2016), 635–638  crossref  mathscinet  zmath  isi  scopus
    18. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 2017, № 1, 80–90  mathnet  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Exact pseudopolynomial algorithm for one sequence partitioning problem”, Autom. Remote Control, 78:1 (2017), 67–74  crossref  isi
    19. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib; A. V. Kel'manov, A. V. Motkova, V. V. Shenmaier, “Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster”, Proc. Steklov Inst. Math. (Suppl.), 303, suppl. 1 (2018), 136–145  crossref  isi
    20. Eremeev A.V. Kel'manov A.V. Pyatkin A.V., “On Complexity of Searching a Subset of Vectors With Shortest Average Under a Cardinality Restriction”, Analysis of Images, Social Networks and Texts, AIST 2016, Communications in Computer and Information Science, 661, ed. Ignatov D. Khachay M. Labunets V. Loukachevitch N. Nikolenko S. Panchenko A. Savchenko A. Vorontsov K., Springer International Publishing Ag, 2017, 51–57  crossref  isi  scopus
    21. Kel'manov A., “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
    22. Kel'manov A. Khamidullin S. Khandeev V., “A Randomized Algorithm For 2-Partition of a Sequence”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, ed. VanDerAalst W. Ignatov D. Khachay M. Kuznetsov S. Lempitsky V. Lomazova I. Loukachevitch N. Napoli A. Panchenko A. Pardalos P. Savchenko A. Wasserman S., Springer International Publishing Ag, 2018, 313–322  crossref  isi  scopus
    23. Kel'manov A. Motkova A. Shenmaier V., “An Approximation Scheme For a Weighted Two-Cluster Partition Problem”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, ed. VanDerAalst W. Ignatov D. Khachay M. Kuznetsov S. Lempitsky V. Lomazova I. Loukachevitch N. Napoli A. Panchenko A. Pardalos P. Savchenko A. Wasserman S., Springer International Publishing Ag, 2018, 323–333  crossref  isi  scopus
    24. А. В. Кельманов, А. В. Пяткин, “NP-трудность некоторых евклидовых задач разбиения конечного множества точек”, Ж. вычисл. матем. и матем. физ., 58:5 (2018), 852–856  mathnet  crossref  elib; A. V. Kel'manov, A. V. Pyatkin, “Np-hardness of some Euclidean problems of partitioning a finite set of points”, Comput. Math. Math. Phys., 58:5 (2018), 822–826  crossref  isi
    25. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 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
    Просмотров:
    Эта страница:305
    Полный текст:97
    Литература:32
    Первая стр.:4
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2022