Abstract:
A strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters is considered. The solution criterion is the minimum of the sum (over both clusters) of weighted sums of squared distances from the elements of each cluster to its geometric center. The weights of the sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other is unknown and is determined as the point of space equal to the mean of the cluster elements. A version of the problem is analyzed in which the cardinalities of the clusters are given as input. A polynomial-time 2-approximation algorithm for solving the problem is constructed.
Citation:
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”, Zh. Vychisl. Mat. Mat. Fiz., 58:1 (2018), 136–142; Comput. Math. Math. Phys., 58:1 (2018), 130–136
\Bibitem{KelMot18}
\by A.~V.~Kel'manov, A.~V.~Motkova
\paper Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
\jour Zh. Vychisl. Mat. Mat. Fiz.
\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}
Linking options:
https://www.mathnet.ru/eng/zvmmf10665
https://www.mathnet.ru/eng/zvmmf/v58/i1/p136
This publication is cited in the following 8 articles:
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
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
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
Citation in format AMSBIB
Contact us: