Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence. / Kel’manov, Alexander; Khamidullin, Sergey; Panasenko, Anna.
Numerical Computations: Theory and Algorithms - 3rd International Conference, NUMTA 2019, Revised Selected Papers. ed. / Yaroslav D. Sergeyev; Dmitri E. Kvasov. Springer Gabler, 2020. p. 386-393 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11974 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence
AU - Kel’manov, Alexander
AU - Khamidullin, Sergey
AU - Panasenko, Anna
N1 - Publisher Copyright: © 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into clusters of the given sizes with some constraints. The solution criterion is the minimum of the sum of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weight of the intracluster sum is equal to the cluster size. The center of one cluster is given as input (is the origin without loss of generality), while the center of the other one is unknown and is determined as a geometric center. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by some given constants. In this paper, we have shown that the considered problem is the strongly NP-hard one and propose a polynomial-time 2-approximation algorithm for solving the problem.
AB - We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into clusters of the given sizes with some constraints. The solution criterion is the minimum of the sum of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weight of the intracluster sum is equal to the cluster size. The center of one cluster is given as input (is the origin without loss of generality), while the center of the other one is unknown and is determined as a geometric center. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by some given constants. In this paper, we have shown that the considered problem is the strongly NP-hard one and propose a polynomial-time 2-approximation algorithm for solving the problem.
KW - Approximation algorithm
KW - Euclidean space
KW - NP-hard problem
KW - Polynomial time
KW - Quadratic variation
KW - Sequence of points
KW - Weighted 2-partition
KW - SERIES DATA
UR - http://www.scopus.com/inward/record.url?scp=85080879437&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-40616-5_34
DO - 10.1007/978-3-030-40616-5_34
M3 - Conference contribution
AN - SCOPUS:85080879437
SN - 9783030406158
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 386
EP - 393
BT - Numerical Computations
A2 - Sergeyev, Yaroslav D.
A2 - Kvasov, Dmitri E.
PB - Springer Gabler
T2 - 3rd Triennial International Conference and Summer School on Numerical Computations: Theory and Algorithms, NUMTA 2019
Y2 - 15 June 2019 through 21 June 2019
ER -
ID: 23740780