Аннотация:
Рассматривается NP-трудная в сильном смысле задача двухкластерного разбиения конечного множества точек евклидова пространства. Критерием решения является минимум суммы по обоим кластерам взвешенных сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Веса сумм равны мощностям искомых кластеров. Центр одного из кластеров задан на входе, а центр другого неизвестен и определяется как точка пространства, равная среднему значению элементов кластера. Анализируется вариант задачи, в котором мощности кластеров заданы на входе. Построен 2-приближенный полиномиальный алгоритм решения задачи. Библ. 25.
Образец цитирования:
А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 136–142; Comput. Math. Math. Phys., 58:1 (2018), 130–136
\RBibitem{KelMot18}
\by А.~В.~Кельманов, А.~В.~Моткова
\paper Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров
\jour Ж. вычисл. матем. и матем. физ.
\yr 2018
\vol 58
\issue 1
\pages 136--142
\mathnet{http://mi.mathnet.ru/zvmmf10665}
\crossref{https://doi.org/10.7868/S0044466918010076}
\elib{https://elibrary.ru/item.asp?id=32282721}
\transl
\jour Comput. Math. Math. Phys.
\yr 2018
\vol 58
\issue 1
\pages 130--136
\crossref{https://doi.org/10.1134/S0965542518010074}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000426674100009}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85042701688}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf10665
https://www.mathnet.ru/rus/zvmmf/v58/i1/p136
Эта публикация цитируется в следующих 8 статьяx:
A. Kel'manov, S. Khamidullin, A. Panasenko, “2-approximation polynomial-time algorithm for a cardinality-weighted 2-partitioning problem of a sequence”, Numerical Computations: Theory and Algorithms, v. II, Lecture Notes in Computer Science, 11974, eds. Y. Sergeyev, D. Kvasov, Springer, 2020, 386–393
A. Kel'manov, S. Khamidullin, A. Panasenko, “Exact algorithm for one cardinality-weighted 2-partitioning problem of a sequence”, Learning and Intelligent Optimization (Lion), Lecture Notes in Computer Science, 11968, eds. N. Matsatsinis, Y. Marinakis, P. Pardalos, Springer, 2020, 135–145
Vladimir Khandeev, Anna Panasenko, Communications in Computer and Information Science, 1275, Mathematical Optimization Theory and Operations Research, 2020, 30
А. В. Кельманов, А. В. Панасенко, В. И. Хандеев, “Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 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
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, 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
Цитирование в формате AMSBIB
Обратная связь: