TY - GEN

T1 - A randomized algorithm for 2-partition of a sequence

AU - Kel’manov, Alexander

AU - Khamidullin, Sergey

AU - Khandeev, Vladimir

PY - 2018/1/1

Y1 - 2018/1/1

N2 - In the paper we consider one strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters minimizing the sum over both clusters of intracluster sum of squared distances from clusters elements to their centers. The cardinalities of clusters are assumed to be given. The center of the first cluster is unknown and is defined as the mean value of all points in the cluster. The center of the second one is the origin. Additionally, the difference between the indexes of two consequent points from the first cluster is bounded from below and above by some constants. A randomized algorithm for the problem is proposed. For an established parameter value, given a relative error ε> 0 and fixed γ∈ (0, 1), this algorithm allows to find a (1 + ε) -approximate solution of the problem with a probability of at least 1 - γ in polynomial time. The conditions are established under which the algorithm is polynomial and asymptotically exact.

AB - In the paper we consider one strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters minimizing the sum over both clusters of intracluster sum of squared distances from clusters elements to their centers. The cardinalities of clusters are assumed to be given. The center of the first cluster is unknown and is defined as the mean value of all points in the cluster. The center of the second one is the origin. Additionally, the difference between the indexes of two consequent points from the first cluster is bounded from below and above by some constants. A randomized algorithm for the problem is proposed. For an established parameter value, given a relative error ε> 0 and fixed γ∈ (0, 1), this algorithm allows to find a (1 + ε) -approximate solution of the problem with a probability of at least 1 - γ in polynomial time. The conditions are established under which the algorithm is polynomial and asymptotically exact.

KW - Asymptotic accuracy

KW - Euclidean space

KW - Minimum sum-of-squared distances

KW - NP-hardness

KW - Partitioning

KW - Randomized algorithm

KW - Sequence

KW - TIME-SERIES DATA

KW - NP-hardness Randomized algorithm

KW - VECTORS

UR - http://www.scopus.com/inward/record.url?scp=85036658365&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-73013-4_29

DO - 10.1007/978-3-319-73013-4_29

M3 - Conference contribution

AN - SCOPUS:85036658365

SN - 9783319730127

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 313

EP - 322

BT - Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers

A2 - VanDerAalst, WMP

A2 - Ignatov, DI

A2 - Khachay, M

A2 - Kuznetsov, SO

A2 - Lempitsky, null

A2 - Lomazova, IA

A2 - Loukachevitch, N

A2 - Napoli, A

A2 - Panchenko, A

A2 - Pardalos, PM

A2 - Savchenko, AV

A2 - Wasserman, S

PB - Springer-Verlag GmbH and Co. KG

T2 - 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017

Y2 - 27 July 2017 through 29 July 2017

ER -