Аннотация:
Рассматривается NP-трудная в сильном смысле задача двухкластерного разбиения конечного множества точек евклидова пространства по критерию минимума суммы по обоим кластерам взвешенных сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Весами сумм являются мощности искомых кластеров. Центр одного из кластеров задан на входе, а центр другого неизвестен и определяется как точка пространства, равная среднему значению элементов кластера (геометрический центр). Анализируются два варианта задачи, в которых мощности кластеров либо неизвестны, либо заданы на входе. Для случая задач, в которых входные данные целочисленны, а размерность пространства фиксирована, построены точные псевдополиномиальные алгоритмы. Библиогр. 24.
Образец цитирования:
А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной 2-кластеризации”, Дискретн. анализ и исслед. опер., 23:3 (2016), 21–34; J. Appl. Industr. Math., 10:3 (2016), 349–355
\RBibitem{KelMot16}
\by А.~В.~Кельманов, А.~В.~Моткова
\paper Точные псевдополиномиальные алгоритмы для задачи сбалансированной $2$-кластеризации
\jour Дискретн. анализ и исслед. опер.
\yr 2016
\vol 23
\issue 3
\pages 21--34
\mathnet{http://mi.mathnet.ru/da850}
\crossref{https://doi.org/10.17377/daio.2016.23.520}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3563714}
\elib{https://elibrary.ru/item.asp?id=26129765}
\transl
\jour J. Appl. Industr. Math.
\yr 2016
\vol 10
\issue 3
\pages 349--355
\crossref{https://doi.org/10.1134/S1990478916030054}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84983502949}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da850
https://www.mathnet.ru/rus/da/v23/i3/p21
Эта публикация цитируется в следующих 15 статьяx:
Anna Panasenko, Communications in Computer and Information Science, 2239, Mathematical Optimization Theory and Operations Research: Recent Trends, 2024, 349
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, ed. N. Matsatsinis, Y. Marinakis, P. Pardalos, Springer, 2020, 135–145
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, Pt II, Lecture Notes in Computer Science, 11974, ed. Y. Sergeyev, D. Kvasov, Springer, 2020, 386–393
Vladimir Khandeev, Anna Panasenko, Communications in Computer and Information Science, 1275, Mathematical Optimization Theory and Operations Research, 2020, 30
A. V. Kel'manov, V. I. Khandeev, A. V. Panasenko, “Exact Algorithms of Search For a Cluster of the Largest Size in Two Integer 2-Clustering Problems”, Numer. 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, ed. 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
А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 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
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. 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, 323–333
A. V. Kel'manov, A. V. Motkova, “Approximation Scheme for a Quadratic Euclidean Weighted 2-Clustering Problem”, Pattern Recognit. Image Anal., 28:1 (2018), 17
Alexander Kel'manov, Vladimir Khandeev, Anna Panasenko, Lecture Notes in Computer Science, 11179, Analysis of Images, Social Networks and Texts, 2018, 294
Alexander Kel'manov, Vladimir Khandeev, Anna Panasenko, Communications in Computer and Information Science, 871, Optimization Problems and Their Applications, 2018, 109
А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 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. 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
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
Цитирование в формате AMSBIB
Обратная связь: