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

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

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



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






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


Дискретн. анализ и исслед. опер., 2010, том 17, номер 2, страницы 39–45 (Mi da604)  

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

К вопросу об алгоритмической сложности одной задачи кластерного анализа

А. В. Долгушевa, А. В. Кельмановba

a Новосибирский гос. университет, Новосибирск, Россия
b Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия

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

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

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

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.2+621.391
Статья поступила: 01.12.2009
Переработанный вариант: 17.12.2009

Образец цитирования: А. В. Долгушев, А. В. Кельманов, “К вопросу об алгоритмической сложности одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 17:2 (2010), 39–45

Цитирование в формате AMSBIB
\RBibitem{DolKel10}
\by А.~В.~Долгушев, А.~В.~Кельманов
\paper К вопросу об алгоритмической сложности одной задачи кластерного анализа
\jour Дискретн. анализ и исслед. опер.
\yr 2010
\vol 17
\issue 2
\pages 39--45
\mathnet{http://mi.mathnet.ru/da604}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2682088}
\zmath{https://zbmath.org/?q=an:1248.62101}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da604
  • http://mi.mathnet.ru/rus/da/v17/i2/p39

    ОТПРАВИТЬ: 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. А. В. Кельманов, А. В. Пяткин, “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
    2. А. В. Кельманов, “$NP$-полнота некоторых задач поиска подмножеств векторов”, Тр. ИММ УрО РАН, 16, № 3, 2010, 121–129  mathnet  elib
    3. А. В. Кельманов, “О сложности некоторых задач анализа данных”, Ж. вычисл. матем. и матем. физ., 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
    4. А. В. Кельманов, “О сложности некоторых задач кластерного анализа”, Ж. вычисл. матем. и матем. физ., 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
    5. А. В. Кельманов, С. М. Романченко, “Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа”, Автомат. и телемех., 2012, № 2, 156–162  mathnet; A. V. Kel'manov, S. M. Romanchenko, “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems”, Autom. Remote Control, 73:2 (2012), 349–354  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$-приближенный алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов”, Автомат. и телемех., 2014, № 4, 5–19  mathnet; A. E. Galashov, A. V. Kel'manov, “A $2$-approximate algorithm to solve one problem of the family of disjoint vector subsets”, Autom. Remote Control, 75:4 (2014), 595–606  crossref  isi
    8. А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 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
    9. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 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
    10. Arrieta Paternina M.R., Zamora-Mendez A., Ortiz-Bejar J., Chow J.H., Ramirez J.M., “Identification of Coherent Trajectories By Modal Characteristics and Hierarchical Agglomerative Clustering”, Electr. Power Syst. Res., 158 (2018), 170–183  crossref  isi  scopus
    11. Kel'manov V A. Panasenko V A. Khandeev I V., “Exact Algorithms of Search For a Cluster of the Largest Size in Two Integer 2-Clustering Problems”, Numer. Anal. Appl., 12:2 (2019), 105–115  mathnet  crossref  mathscinet  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:500
    Полный текст:93
    Литература:40
    Первая стр.:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021