This article is cited in 4 scientific papers (total in 4 papers)
Fully polynomial-time approximation scheme for a sequence $2$-clustering problem
A. V. Kel'manovab, S. A. Khamidullinb, V. I. Khandeevb
a Novosibirsk State University, 2 Pirogova St., 630090 Novosibirsk, Russia
b Sobolev Institute of Mathematics, 4 Koptyug Ave., 630090 Novosibirsk, Russia
We consider a strongly NP-hard problem of partitioning a finite sequence of points in Euclidean space into two clusters minimizing the sum over both clusters of intra-cluster sum of squared distances from the clusters elements to their centers. The sizes of the clusters are fixed. The centroid of the first cluster is defined as the mean value of all vectors in the cluster, and the center of the second one is given in advance and
is equal to 0. Additionally, the partition must satisfy the restriction that for all vectors in the first cluster the difference between the indices of two consequent points from this cluster is bounded from below and above by
some given constants. We present a fully polynomial-time approximation scheme for the case of fixed space dimension. Bibliogr. 27.
partitioning, sequence, Euclidean space, minimum sum-of-squared distances, NP-hardness, FPTAS.
PDF file (299 kB)
Journal of Applied and Industrial Mathematics, 2016, 10:2, 209–219
A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, Diskretn. Anal. Issled. Oper., 23:2 (2016), 21–40; J. Appl. Industr. Math., 10:2 (2016), 209–219
Citation in format AMSBIB
\by A.~V.~Kel'manov, S.~A.~Khamidullin, V.~I.~Khandeev
\paper Fully polynomial-time approximation scheme for a~sequence $2$-clustering problem
\jour Diskretn. Anal. Issled. Oper.
\jour J. Appl. Industr. Math.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96
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. 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. 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. 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, 313–322
|Number of views:|