|
|
Дискретн. анализ и исслед. опер., 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Ю. Ю. Великанова, “Алгоритмы для одной задачи о нахождении максимума унимодальной функции в режиме online”, Дискретн. анализ и исслед. опер., 20:6 (2013), 16–29
 -
А. В. Кельманов, С. А. Хамидуллин, “Приближённый полиномиальный алгоритм для одной задачи разбиения последовательности”, Дискретн. анализ и исслед. опер., 21:1 (2014), 53–66 ; A. V. Kelmanov, S. A. Khamidullin, “Approximation algorithm for one problem of partitioning a sequence”, J. Appl. Industr. Math., 8:2 (2014), 236–244
-
А. А. Агеев, А. В. Кельманов, А. В. Пяткин, “Cложность задачи о разрезе максимального веса в евклидовом пространстве”, Дискретн. анализ и исслед. опер., 21:4 (2014), 3–11 ; 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
-
А. В. Орлов, “Численный поиск глобальных решений в задачах несимметричной билинейной отделимости”, Дискретн. анализ и исслед. опер., 22:1 (2015), 64–85
 -
А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 55:2 (2015), 335–344 ; 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
 -
А. В. Кельманов, С. А. Хамидуллин, “Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности”, Ж. вычисл. матем. и матем. физ., 55:6 (2015), 1076–1085 ; 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
-
А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62 ; 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
-
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40 ; 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
-
А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность”, Тр. ИММ УрО РАН, 22, № 3, 2016, 144–152 ; 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
-
А. В. Еремеев, А. В. Кельманов, А. В. Пяткин, “О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования”, Ж. вычисл. матем. и матем. физ., 56:10 (2016), 1831–1836 ; 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
-
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 2017, № 1, 80–90 ; 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
-
А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры”, Ж. вычисл. матем. и матем. физ., 57:8 (2017), 1392–1400 ; 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
-
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
-
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 58:12 (2018), 2169–2178 ; 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
-
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
|
| Просмотров: |
| Эта страница: | 279 | | Полный текст: | 59 | | Литература: | 36 | | Первая стр.: | 10 |
|
Пользовательское соглашение