|
|
Дискретн. анализ и исслед. опер., 2013, том 20, номер 4, страницы 36–45
(Mi da738)
|
 |
|
 |
Эта публикация цитируется в 10 научных статьях (всего в 10 статьях)
Полиномиальный алгоритм с оценкой точности $2$ для решения одной задачи кластерного анализа
А. В. Кельмановab, В. И. Хандеевb
a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2,
630090 Новосибирск, Россия
Аннотация:
Предложен $2$-приближённый полиномиальный алгоритм для труднорешаемой задачи, к которой сводится одна из проблем разбиения конечного множества векторов евклидова пространства на два подмножества (кластера) по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Центром первого кластера является среднее значение векторов в этом кластере, а центром второго – нуль-вектор. Библиогр. 16.
Ключевые слова:
кластерный анализ, поиск подмножества векторов, алгоритмическая сложность, полиномиальный приближённый алгоритм.
 Полный текст:
PDF файл (244 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2013, 7:4, 515–521
Реферативные базы данных:
Тип публикации:
Статья
УДК:
519.2+621.391
Статья поступила: 12.06.2012
Переработанный вариант: 21.10.2012
Образец цитирования:
А. В. Кельманов, В. И. Хандеев, “Полиномиальный алгоритм с оценкой точности $2$ для решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 20:4 (2013), 36–45; J. Appl. Industr. Math., 7:4 (2013), 515–521
Цитирование в формате AMSBIB
\RBibitem{KelKha13}
\by А.~В.~Кельманов, В.~И.~Хандеев
\paper Полиномиальный алгоритм с~оценкой точности~$2$ для решения одной задачи кластерного анализа
\jour Дискретн. анализ и исслед. опер.
\yr 2013
\vol 20
\issue 4
\pages 36--45
\mathnet{http://mi.mathnet.ru/da738}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3114911}
\transl
\jour J. Appl. Industr. Math.
\yr 2013
\vol 7
\issue 4
\pages 515--521
\crossref{https://doi.org/10.1134/S1990478913040066}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da738 http://mi.mathnet.ru/rus/da/v20/i4/p36
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
А. В. Орлов, “Численный поиск глобальных решений в задачах несимметричной билинейной отделимости”, Дискретн. анализ и исслед. опер., 22:1 (2015), 64–85
  -
А. В. Кельманов, С. А. Хамидуллин, “Приближенный полиномиальный алгоритм для одной задачи бикластеризации последовательности”, Ж. вычисл. матем. и матем. физ., 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
-
А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 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
-
А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:2 (2016), 332–340 ; 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
-
А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $2$-кластеризации”, Дискретн. анализ и исслед. опер., 23:3 (2016), 21–34 ; A. V. Kel'manov, A. V. Motkova, “Exact pseudopolinomial algorithms for a balanced $2$-clustering problem”, J. Appl. Industr. Math., 10:3 (2016), 349–355
-
A. Kel'manov, V. Khandeev, “Some algorithms with guaranteed accuracy for 2-clustering problems with given center of one cluster”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 91–93
-
A. Kel'manov, A. Motkova, “An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 94–96
-
A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “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. D. Ignatov, M. Khachay, V. Labunets, N. Loukachevitch, S. Nikolenko, A. Panchenko, A. Savchenko, K. Vorontsov, Springler, 2017, 51–57
 -
А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 136–142 ; A. V. Kel'manov, A. V. Motkova, “Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center”, Comput. Math. Math. Phys., 58:1 (2018), 130–136
|
| Просмотров: |
| Эта страница: | 225 | | Полный текст: | 72 | | Литература: | 39 | | Первая стр.: | 3 |
|
Пользовательское соглашение