Abstract:
We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The center of one cluster is unknown and is defined as the mean value of its elements (i.e., it is the centroid of the cluster). The center of the other cluster is fixed at the origin. The weight factors for the intracluster sums are given as input. We present an approximation algorithm for this problem, which is based on the adaptive grid approach to finding the center of the optimal cluster. We show that the algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of fixed space dimension. If the dimension is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm realizes a polynomial-time approximation scheme (PTAS).
Citation:
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”, Trudy Inst. Mat. i Mekh. UrO RAN, 23, no. 3, 2017, 159–170; Proc. Steklov Inst. Math. (Suppl.), 303, suppl. 1 (2018), 136–145
\Bibitem{KelMotShe17}
\by A.~V.~Kel'manov, A.~V.~Motkova, V.~V.~Shenmaier
\paper Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2017
\vol 23
\issue 3
\pages 159--170
\mathnet{http://mi.mathnet.ru/timm1446}
\crossref{https://doi.org/10.21538/0134-4889-2017-23-3-159-170}
\elib{https://elibrary.ru/item.asp?id=29938008}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2018
\vol 303
\issue , suppl. 1
\pages 136--145
\crossref{https://doi.org/10.1134/S0081543818090146}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000453521100014}
Linking options:
https://www.mathnet.ru/eng/timm1446
https://www.mathnet.ru/eng/timm/v23/i3/p159
This publication is cited in the following 2 articles:
Anna Panasenko, Communications in Computer and Information Science, 2239, Mathematical Optimization Theory and Operations Research: Recent Trends, 2024, 349
Vladimir Shenmaier, “Linear-size universal discretization of geometric center-based problems in fixed dimensions”, J Comb Optim, 43:3 (2022), 528