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

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

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



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






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


Дискретн. анализ и исслед. опер., 2013, том 20, номер 2, страницы 47–57 (Mi da725)  

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

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

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

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

Аннотация: Доказана NP-полнота двух задач кластеризации (разбиения) конечной последовательности векторов евклидова пространства. В оптимизационных вариантах обеих задач требуется разбить элементы последовательности на фиксированное число кластеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. В одной из задач мощности кластеров заданы на входе задачи, а в другой неизвестны (являются оптимизируемыми величинами). За исключением центра одного (специального кластера) центры остальных кластеров определяются как средние значения по всем векторам, образующим эти кластеры. Центр специального кластера полагается равным нулю. При этом разбиение подчинено условию: для всех векторов, не входящих в специальный кластер, разность между номерами последующего и предыдущего векторов, входящих в любой из этих кластеров, ограничена сверху и снизу заданными константами. Библиогр. 20.

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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2013, 7:3, 363–369

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

Тип публикации: Статья
УДК: 519.2+621.391
Статья поступила: 27.06.2012
Переработанный вариант: 11.10.2012

Образец цитирования: А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач кластерного анализа векторных последовательностей”, Дискретн. анализ и исслед. опер., 20:2 (2013), 47–57; J. Appl. Industr. Math., 7:3 (2013), 363–369

Цитирование в формате AMSBIB
\RBibitem{KelPya13}
\by А.~В.~Кельманов, А.~В.~Пяткин
\paper О сложности некоторых задач кластерного анализа векторных последовательностей
\jour Дискретн. анализ и исслед. опер.
\yr 2013
\vol 20
\issue 2
\pages 47--57
\mathnet{http://mi.mathnet.ru/da725}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3113400}
\transl
\jour J. Appl. Industr. Math.
\yr 2013
\vol 7
\issue 3
\pages 363--369
\crossref{https://doi.org/10.1134/S1990478913030095}


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

    ОТПРАВИТЬ: 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. Ю. Ю. Великанова, “Алгоритмы для одной задачи о нахождении максимума унимодальной функции в режиме online”, Дискретн. анализ и исслед. опер., 20:6 (2013), 16–29  mathnet  mathscinet
    2. А. В. Кельманов, С. А. Хамидуллин, “Приближённый полиномиальный алгоритм для одной задачи разбиения последовательности”, Дискретн. анализ и исслед. опер., 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
    3. А. А. Агеев, А. В. Кельманов, А. В. Пяткин, “Cложность задачи о разрезе максимального веса в евклидовом пространстве”, Дискретн. анализ и исслед. опер., 21:4 (2014), 3–11  mathnet  mathscinet; A. A. Ageev, A. V. Kel'manov, A. V. Pyatkin, “Complexity of the Euclidean max cut problem”, J. Appl. Industr. Math., 8:4 (2014), 453–457  crossref
    4. А. В. Орлов, “Численный поиск глобальных решений в задачах несимметричной билинейной отделимости”, Дискретн. анализ и исслед. опер., 22:1 (2015), 64–85  mathnet  crossref  mathscinet  elib
    5. А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 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
    6. А. В. Кельманов, С. А. Хамидуллин, “Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности”, Ж. вычисл. матем. и матем. физ., 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
    7. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 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
    8. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 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
    9. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность”, Тр. ИММ УрО РАН, 22, № 3, 2016, 144–152  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96  crossref  isi
    10. А. В. Еремеев, А. В. Кельманов, А. В. Пяткин, “О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования”, Ж. вычисл. матем. и матем. физ., 56:10 (2016), 1831–1836  mathnet  crossref  elib; A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On the complexity and approximability of some Euclidean optimal summing problems”, Comput. Math. Math. Phys., 56:10 (2016), 1813–1817  crossref  isi
    11. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 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
    12. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры”, Ж. вычисл. матем. и матем. физ., 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
    13. 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
    14. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 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
    15. A. Kel'manov, S. Khamidullin, V. Khandeev, “A randomized algorithm for 2-partition of a sequence”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 313–322  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:279
    Полный текст:59
    Литература:36
    Первая стр.:10
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019