Standard

Randomized algorithms for some sequence clustering problems. / Khamidullin, Sergey; Khandeev, Vladimir; Panasenko, Anna.

Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers. ed. / Ilias S. Kotsireas; Panos M. Pardalos. Springer Gabler, 2020. p. 96-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12096 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Khamidullin, S, Khandeev, V & Panasenko, A 2020, Randomized algorithms for some sequence clustering problems. in IS Kotsireas & PM Pardalos (eds), Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12096 LNCS, Springer Gabler, pp. 96-101, 14th International Conference on Learning and Intelligent Optimization, LION 2020, Athens, Greece, 24.05.2020. https://doi.org/10.1007/978-3-030-53552-0_11

APA

Khamidullin, S., Khandeev, V., & Panasenko, A. (2020). Randomized algorithms for some sequence clustering problems. In I. S. Kotsireas, & P. M. Pardalos (Eds.), Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers (pp. 96-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12096 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-53552-0_11

Vancouver

Khamidullin S, Khandeev V, Panasenko A. Randomized algorithms for some sequence clustering problems. In Kotsireas IS, Pardalos PM, editors, Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers. Springer Gabler. 2020. p. 96-101. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-53552-0_11

Author

Khamidullin, Sergey ; Khandeev, Vladimir ; Panasenko, Anna. / Randomized algorithms for some sequence clustering problems. Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers. editor / Ilias S. Kotsireas ; Panos M. Pardalos. Springer Gabler, 2020. pp. 96-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{d154c8cbfc9d4457b42762e7dea2c037,
title = "Randomized algorithms for some sequence clustering problems",
abstract = "We consider two problems of clustering a finite sequence of points in Euclidean space. In the first problem, we need to find a cluster minimizing intracluster sum of squared distances from cluster elements to its centroid. In the second problem, we need to partition a sequence into two clusters minimizing cardinality-weighted intracluster sums of squared distances from clusters elements to their centers; the center of the first cluster is its centroid, while the center of the second one is the origin. Moreover, in the first problem, the difference between any two subsequent indices of cluster elements is bounded above and below by some constants. In the second problem, the same constraint is imposed on the cluster with unknown centroid. We present randomized algorithms for both problems and find the conditions under which these algorithms are polynomial and asymptotically exact.",
keywords = "Asymptotic accuracy, Clustering, Euclidean space, Minimum sum-of-squares, NP-hard problem, Randomized algorithm",
author = "Sergey Khamidullin and Vladimir Khandeev and Anna Panasenko",
year = "2020",
month = jun,
day = "1",
doi = "10.1007/978-3-030-53552-0_11",
language = "English",
isbn = "9783030535513",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Gabler",
pages = "96--101",
editor = "Kotsireas, {Ilias S.} and Pardalos, {Panos M.}",
booktitle = "Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers",
address = "Germany",
note = "14th International Conference on Learning and Intelligent Optimization, LION 2020 ; Conference date: 24-05-2020 Through 28-05-2020",

}

RIS

TY - GEN

T1 - Randomized algorithms for some sequence clustering problems

AU - Khamidullin, Sergey

AU - Khandeev, Vladimir

AU - Panasenko, Anna

PY - 2020/6/1

Y1 - 2020/6/1

N2 - We consider two problems of clustering a finite sequence of points in Euclidean space. In the first problem, we need to find a cluster minimizing intracluster sum of squared distances from cluster elements to its centroid. In the second problem, we need to partition a sequence into two clusters minimizing cardinality-weighted intracluster sums of squared distances from clusters elements to their centers; the center of the first cluster is its centroid, while the center of the second one is the origin. Moreover, in the first problem, the difference between any two subsequent indices of cluster elements is bounded above and below by some constants. In the second problem, the same constraint is imposed on the cluster with unknown centroid. We present randomized algorithms for both problems and find the conditions under which these algorithms are polynomial and asymptotically exact.

AB - We consider two problems of clustering a finite sequence of points in Euclidean space. In the first problem, we need to find a cluster minimizing intracluster sum of squared distances from cluster elements to its centroid. In the second problem, we need to partition a sequence into two clusters minimizing cardinality-weighted intracluster sums of squared distances from clusters elements to their centers; the center of the first cluster is its centroid, while the center of the second one is the origin. Moreover, in the first problem, the difference between any two subsequent indices of cluster elements is bounded above and below by some constants. In the second problem, the same constraint is imposed on the cluster with unknown centroid. We present randomized algorithms for both problems and find the conditions under which these algorithms are polynomial and asymptotically exact.

KW - Asymptotic accuracy

KW - Clustering

KW - Euclidean space

KW - Minimum sum-of-squares

KW - NP-hard problem

KW - Randomized algorithm

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

U2 - 10.1007/978-3-030-53552-0_11

DO - 10.1007/978-3-030-53552-0_11

M3 - Conference contribution

AN - SCOPUS:85089213553

SN - 9783030535513

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

SP - 96

EP - 101

BT - Learning and Intelligent Optimization - 14th International Conference, LION 14, 2020, Revised Selected Papers

A2 - Kotsireas, Ilias S.

A2 - Pardalos, Panos M.

PB - Springer Gabler

T2 - 14th International Conference on Learning and Intelligent Optimization, LION 2020

Y2 - 24 May 2020 through 28 May 2020

ER -

ID: 24956058