А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 55:2 (2015), 335–344; Comput. Math. Math. Phys., 55:2 (2015), 330

Журнал вычислительной математики и математической физики

RUS ENG

ЖУРНАЛЫ ПЕРСОНАЛИИ ОРГАНИЗАЦИИ КОНФЕРЕНЦИИ СЕМИНАРЫ ВИДЕОТЕКА ПАКЕТ AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	Общая информация
	Последний выпуск
	Архив
	Импакт-фактор

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

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

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

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

Журнал вычислительной математики и математической физики, 2015, том 55, номер 2, страницы 335–344
DOI: https://doi.org/10.7868/S0044466915020131 (Mi zvmmf10162)

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

Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов

А. В. Кельманов^ab, В. И. Хандеев^a

^a 630090 Новосибирск, пр. Ак. Коптюга, 4, Ин-т математики СО РАН
^b 630090 Новосибирск, ул. Пирогова, 2, Новосибирск. гос. ун-т

PDF полного текста (240 kB) Список цитирования (28)

Список литературы:

PDF

HTML

DOI: https://doi.org/10.7868/S0044466915020131

Аннотация: Обоснован рандомизированный алгоритм для NP-трудной в сильном смысле задачи разбиения конечного множества векторов евклидова пространства на два кластера заданных размеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из кластеров является оптимизируемой величиной и определяется как среднее значение по всем векторам, образующим этот кластер. Центр другого кластера фиксирован в начале координат. Предложенный алгоритм при заданных относительной ошибке и вероятности несрабатывания для установленного значения параметра находит приближенное решение задачи за линейное от размерности пространства и размера входа задачи время. Найдены условия, при которых алгоритм асимптотически точен и позволяет находить решение за время, линейное от размерности пространства и квадратичное от размера входа задачи. Библ. 23.

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

Финансовая поддержка	Номер гранта
Российский фонд фундаментальных исследований	15-00-00462 13-07-00070
Работа выполнена при финансовой поддержке РФФИ (коды проектов 15-00-00462, 13-07-00070).

Поступила в редакцию: 12.03.2014

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2015, Volume 55, Issue 2, Pages 330–339
DOI: https://doi.org/10.1134/S096554251502013X

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

Тип публикации: Статья

УДК: 519.7

Образец цитирования: А. В. Кельманов, В. И. Хандеев, “Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Ж. вычисл. матем. и матем. физ., 55:2 (2015), 335–344; Comput. Math. Math. Phys., 55:2 (2015), 330–339

Цитирование в формате AMSBIB

\RBibitem{KelKha15}

\by А.~В.~Кельманов, В.~И.~Хандеев

\paper Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов

\jour Ж. вычисл. матем. и матем. физ.

\yr 2015

\vol 55

\issue 2

\pages 335--344

\mathnet{http://mi.mathnet.ru/zvmmf10162}

\crossref{https://doi.org/10.7868/S0044466915020131}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3317887}

\elib{https://elibrary.ru/item.asp?id=22908475}

\transl

\jour Comput. Math. Math. Phys.

\yr 2015

\vol 55

\issue 2

\pages 330--339

\crossref{https://doi.org/10.1134/S096554251502013X}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000350801800017}

\elib{https://elibrary.ru/item.asp?id=24011263}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84924119914}

Образцы ссылок на эту страницу:

https://www.mathnet.ru/rus/zvmmf10162

https://www.mathnet.ru/rus/zvmmf/v55/i2/p335

Эта публикация цитируется в следующих 28 статьяx:

A. L. Reznik, A. A. Soloviev, “Solving Fundamental and Applied Problems of Digital Image Processing at the Institute of Automation and Electrometry and Other Scientific Schools of the Siberian Branch of the Russian Academy of Sciences”, Pattern Recognit. Image Anal., 33:4 (2023), 1260
А. В. Кельманов, А. В. Панасенко, В. И. Хандеев, “Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 2-кластеризации”, Сиб. журн. вычисл. матем., 22:2 (2019), 121–136 ; A. V. Kel'manov, A. V. Panasenko, V. I. Khandeev, “Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems”, Num. Anal. Appl., 12:2 (2019), 105–115
А. В. Кельманов, А. В. Пяткин, В. И. Хандеев, “Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость”, Тр. ИММ УрО РАН, 25, № 4, 2019, 69–78 ; A. V. Kel'manov, A. V. Pyatkin, V. I. Khandeev, “Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with Constraints on the Size of the Clusters: Complexity and Approximability”, Proc. Steklov Inst. Math. (Suppl.), 313, suppl. 1 (2021), S117–S124
A. Panasenko, “A PTAS for one cardinality-weighted 2-clustering problem”, Mathematical Optimization Theory and Operations Research, Lecture Notes in Computer Science, 11548, eds. M. Khachay, Y. Kochetov, P. Pardalos, Springer, 2019, 581–592
А. В. Кельманов, А. В. Панасенко, В. И. Хандеев, “Рандомизированные алгоритмы для некоторых труднорешаемых задач кластеризации конечного множества точек евклидова пространства”, Ж. вычисл. матем. и матем. физ., 59:5 (2019), 895–904 ; A. V. Kel'manov, A. V. Panasenko, V. I. Khandeev, “Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space”, Comput. Math. Math. Phys., 59:5 (2019), 842–850
Alexander Kel'manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin, Communications in Computer and Information Science, 974, Optimization and Applications, 2019, 131
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. VanDerAalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, Springer, 2018, 313–322
A. Kel'manov, A. Motkova, V. Shenmaier, “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, eds. W. VanDerAalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 323–333
А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 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
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 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. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, A. V. Pyatkin, “An Exact Algorithm of Searching for the Largest Cluster in an Integer-Valued Problem of 2-Partitioning a Sequence”, Pattern Recognit. Image Anal., 28:4 (2018), 703
Alexander Kel'manov, Vladimir Khandeev, Anna Panasenko, Communications in Computer and Information Science, 871, Optimization Problems and Their Applications, 2018, 109
Alexander Kel'manov, Vladimir Khandeev, Anna Panasenko, Lecture Notes in Computer Science, 11179, Analysis of Images, Social Networks and Texts, 2018, 294
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 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
А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170 ; 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
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, eds. D. Ignatov, M. Khachay, V. Labunets, N. Loukachevitch, S. Nikolenko, A. Panchenko, A. Savchenko, K. , Springer, 2017, 51–57
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 2017, 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 2017, IEEE, 2017, 94–96
А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 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
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 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

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Журнал вычислительной математики и математической физики

Computational Mathematics and Mathematical Physics

Статистика просмотров:
Страница аннотации:	387
PDF полного текста:	78
Список литературы:	85
Первая страница:	19

Что такое QR-код?

Обратная связь:
math-net2025_03@mi-ras.ru

Пользовательское соглашение

Регистрация посетителей портала

Логотипы