Standard
A randomized algorithm for 2-partition of a sequence. / Kel’manov, Alexander; Khamidullin, Sergey; Khandeev, Vladimir.
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. ed. / WMP VanDerAalst; DI Ignatov; M Khachay; SO Kuznetsov; Lempitsky; IA Lomazova; N Loukachevitch; A Napoli; A Panchenko; PM Pardalos; AV Savchenko; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. p. 313-322 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Kel’manov, A, Khamidullin, S
& Khandeev, V 2018,
A randomized algorithm for 2-partition of a sequence. in WMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko & S Wasserman (eds),
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10716 LNCS, Springer-Verlag GmbH and Co. KG, pp. 313-322, 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017, Moscow, Russian Federation,
27.07.2017.
https://doi.org/10.1007/978-3-319-73013-4_29
APA
Kel’manov, A., Khamidullin, S.
, & Khandeev, V. (2018).
A randomized algorithm for 2-partition of a sequence. In WMP. VanDerAalst, DI. Ignatov, M. Khachay, SO. Kuznetsov, Lempitsky, IA. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, PM. Pardalos, AV. Savchenko, & S. Wasserman (Eds.),
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers (pp. 313-322). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-319-73013-4_29
Vancouver
Kel’manov A, Khamidullin S
, Khandeev V.
A randomized algorithm for 2-partition of a sequence. In VanDerAalst WMP, Ignatov DI, Khachay M, Kuznetsov SO, Lempitsky, Lomazova IA, Loukachevitch N, Napoli A, Panchenko A, Pardalos PM, Savchenko AV, Wasserman S, editors, Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2018. p. 313-322. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-73013-4_29
Author
Kel’manov, Alexander ; Khamidullin, Sergey
; Khandeev, Vladimir. /
A randomized algorithm for 2-partition of a sequence. Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. editor / WMP VanDerAalst ; DI Ignatov ; M Khachay ; SO Kuznetsov ; Lempitsky ; IA Lomazova ; N Loukachevitch ; A Napoli ; A Panchenko ; PM Pardalos ; AV Savchenko ; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. pp. 313-322 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{2814262a2b694e3bab793e8f61bf8b4c,
title = "A randomized algorithm for 2-partition of a sequence",
abstract = "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.",
keywords = "Asymptotic accuracy, Euclidean space, Minimum sum-of-squared distances, NP-hardness, Partitioning, Randomized algorithm, Sequence, TIME-SERIES DATA, NP-hardness Randomized algorithm, VECTORS",
author = "Alexander Kel{\textquoteright}manov and Sergey Khamidullin and Vladimir Khandeev",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-73013-4_29",
language = "English",
isbn = "9783319730127",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "313--322",
editor = "WMP VanDerAalst and DI Ignatov and M Khachay and SO Kuznetsov and Lempitsky and IA Lomazova and N Loukachevitch and A Napoli and A Panchenko and PM Pardalos and AV Savchenko and S Wasserman",
booktitle = "Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers",
address = "Germany",
note = "6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 ; Conference date: 27-07-2017 Through 29-07-2017",
}
RIS
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 -