Standard

A Randomized Algorithm for a Sequence 2-Clustering Problem. / Kel'manov, A. V.; Khamidullin, S. A.; Khandeev, V. I.

In: Computational Mathematics and Mathematical Physics, Vol. 58, No. 12, 01.01.2018, p. 2078-2085.

Research output: Contribution to journal › Article › peer-review

Harvard

Kel'manov, AV, Khamidullin, SA & Khandeev, VI 2018, 'A Randomized Algorithm for a Sequence 2-Clustering Problem', Computational Mathematics and Mathematical Physics, vol. 58, no. 12, pp. 2078-2085. https://doi.org/10.1134/S0965542518120138

APA

Kel'manov, A. V., Khamidullin, S. A., & Khandeev, V. I. (2018). A Randomized Algorithm for a Sequence 2-Clustering Problem. Computational Mathematics and Mathematical Physics, 58(12), 2078-2085. https://doi.org/10.1134/S0965542518120138

Vancouver

Kel'manov AV, Khamidullin SA, Khandeev VI. A Randomized Algorithm for a Sequence 2-Clustering Problem. Computational Mathematics and Mathematical Physics. 2018 Jan 1;58(12):2078-2085. doi: 10.1134/S0965542518120138

Author

Kel'manov, A. V. ; Khamidullin, S. A. ; Khandeev, V. I. / A Randomized Algorithm for a Sequence 2-Clustering Problem. In: Computational Mathematics and Mathematical Physics. 2018 ; Vol. 58, No. 12. pp. 2078-2085.

BibTeX

@article{c80ba78dff0445e298c44c99ea93bce8,
title = "A Randomized Algorithm for a Sequence 2-Clustering Problem",
abstract = "We consider a strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters of given cardinalities minimizing the sum over both clusters of intracluster sums of squared distances from clusters elements to their centers. The center of one cluster is unknown and is defined as the mean value of all points in the cluster. The center of the other cluster is the origin. Additionally, the difference between the indices of two consequent points from the first cluster is bounded from below and above by some constants. A randomized algorithm that finds an approximation solution of the problem in polynomial time for given values of the relative error and failure probability and for an established parameter value is proposed. The conditions are established under which the algorithm is polynomial and asymptotically exact.",
keywords = "partitioning, sequence, Euclidean space, minimum sum-of-squared distances, NP-hardness, randomized algorithm, asymptotic accuracy, Asymptotic accuracy, Partitioning, Sequence, Randomized algorithm, Minimum sum-of-squared distances",
author = "Kel'manov, {A. V.} and Khamidullin, {S. A.} and Khandeev, {V. I.}",
year = "2018",
month = jan,
day = "1",
doi = "10.1134/S0965542518120138",
language = "English",
volume = "58",
pages = "2078--2085",
journal = "Computational Mathematics and Mathematical Physics",
issn = "0965-5425",
publisher = "PLEIADES PUBLISHING INC",
number = "12",

}

RIS

TY - JOUR

T1 - A Randomized Algorithm for a Sequence 2-Clustering Problem

AU - Kel'manov, A. V.

AU - Khamidullin, S. A.

AU - Khandeev, V. I.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We consider a strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters of given cardinalities minimizing the sum over both clusters of intracluster sums of squared distances from clusters elements to their centers. The center of one cluster is unknown and is defined as the mean value of all points in the cluster. The center of the other cluster is the origin. Additionally, the difference between the indices of two consequent points from the first cluster is bounded from below and above by some constants. A randomized algorithm that finds an approximation solution of the problem in polynomial time for given values of the relative error and failure probability and for an established parameter value is proposed. The conditions are established under which the algorithm is polynomial and asymptotically exact.

AB - We consider a strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters of given cardinalities minimizing the sum over both clusters of intracluster sums of squared distances from clusters elements to their centers. The center of one cluster is unknown and is defined as the mean value of all points in the cluster. The center of the other cluster is the origin. Additionally, the difference between the indices of two consequent points from the first cluster is bounded from below and above by some constants. A randomized algorithm that finds an approximation solution of the problem in polynomial time for given values of the relative error and failure probability and for an established parameter value is proposed. The conditions are established under which the algorithm is polynomial and asymptotically exact.

KW - partitioning

KW - sequence

KW - Euclidean space

KW - minimum sum-of-squared distances

KW - NP-hardness

KW - randomized algorithm

KW - asymptotic accuracy

KW - Asymptotic accuracy

KW - Partitioning

KW - Sequence

KW - Randomized algorithm

KW - Minimum sum-of-squared distances

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

U2 - 10.1134/S0965542518120138

DO - 10.1134/S0965542518120138

M3 - Article

VL - 58

SP - 2078

EP - 2085

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 12

ER -

ID: 18631871