Standard

An Exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem. / Kel’manov, Alexander; Khamidullin, Sergey; Khandeev, Vladimir et al.

Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. ed. / Yury Kochetov; Michael Khachay; Yury Evtushenko; Vlasta Malkova; Mikhail Posypkin; Milojica Jacimovic. Springer-Verlag GmbH and Co. KG, 2019. p. 131-143 (Communications in Computer and Information Science; Vol. 974).

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

Harvard

Kel’manov, A, Khamidullin, S, Khandeev, V & Pyatkin, A 2019, An Exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem. in Y Kochetov, M Khachay, Y Evtushenko, V Malkova, M Posypkin & M Jacimovic (eds), Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. Communications in Computer and Information Science, vol. 974, Springer-Verlag GmbH and Co. KG, pp. 131-143, 9th International Conference on Optimization and Applications, OPTIMA 2018, Petrovac, Montenegro, 01.10.2018. https://doi.org/10.1007/978-3-030-10934-9_10

APA

Kel’manov, A., Khamidullin, S., Khandeev, V., & Pyatkin, A. (2019). An Exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem. In Y. Kochetov, M. Khachay, Y. Evtushenko, V. Malkova, M. Posypkin, & M. Jacimovic (Eds.), Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers (pp. 131-143). (Communications in Computer and Information Science; Vol. 974). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-10934-9_10

Vancouver

Kel’manov A, Khamidullin S, Khandeev V, Pyatkin A. An Exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem. In Kochetov Y, Khachay M, Evtushenko Y, Malkova V, Posypkin M, Jacimovic M, editors, Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2019. p. 131-143. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-10934-9_10

Author

Kel’manov, Alexander ; Khamidullin, Sergey ; Khandeev, Vladimir et al. / An Exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem. Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers. editor / Yury Kochetov ; Michael Khachay ; Yury Evtushenko ; Vlasta Malkova ; Mikhail Posypkin ; Milojica Jacimovic. Springer-Verlag GmbH and Co. KG, 2019. pp. 131-143 (Communications in Computer and Information Science).

BibTeX

@inproceedings{005d554b52024e6c84efd737da56d681,
title = "An Exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem",
abstract = "A problem of partitioning a finite sequence of points in Euclidean space into two subsequences (clusters) maximizing the size of the first cluster subject to two constraints is considered. The first constraint deals with every two consecutive indices of elements of the first cluster: the difference between them is bounded from above and below by some constants. The second one restricts the value of a quadratic clustering function that is the sum of the intracluster sums over both clusters. The intracluster sum is the sum of squared distances between cluster elements and the cluster center. The center of the first cluster is unknown and determined as the centroid (i.e. as the mean value of its elements), while the center of the second one is zero. The strong NP-hardness of the problem is shown and an exact algorithm is suggested for the case of integer coordinates of input points. If the space dimension is bounded by some constant this algorithm runs in a pseudopolynomial time.",
keywords = "2-partition, Euclidean space, Exact algorithm, Fixed space dimension, Integer coordinates, Longest subsequence, NP-hard problem, Pseudopolynomial running time, Quadratic variance, Sequence",
author = "Alexander Kel{\textquoteright}manov and Sergey Khamidullin and Vladimir Khandeev and Artem Pyatkin",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-10934-9_10",
language = "English",
isbn = "9783030109332",
series = "Communications in Computer and Information Science",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "131--143",
editor = "Yury Kochetov and Michael Khachay and Yury Evtushenko and Vlasta Malkova and Mikhail Posypkin and Milojica Jacimovic",
booktitle = "Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers",
address = "Germany",
note = "9th International Conference on Optimization and Applications, OPTIMA 2018 ; Conference date: 01-10-2018 Through 05-10-2018",

}

RIS

TY - GEN

T1 - An Exact algorithm of searching for the largest size cluster in an integer sequence 2-clustering problem

AU - Kel’manov, Alexander

AU - Khamidullin, Sergey

AU - Khandeev, Vladimir

AU - Pyatkin, Artem

PY - 2019/1/1

Y1 - 2019/1/1

N2 - A problem of partitioning a finite sequence of points in Euclidean space into two subsequences (clusters) maximizing the size of the first cluster subject to two constraints is considered. The first constraint deals with every two consecutive indices of elements of the first cluster: the difference between them is bounded from above and below by some constants. The second one restricts the value of a quadratic clustering function that is the sum of the intracluster sums over both clusters. The intracluster sum is the sum of squared distances between cluster elements and the cluster center. The center of the first cluster is unknown and determined as the centroid (i.e. as the mean value of its elements), while the center of the second one is zero. The strong NP-hardness of the problem is shown and an exact algorithm is suggested for the case of integer coordinates of input points. If the space dimension is bounded by some constant this algorithm runs in a pseudopolynomial time.

AB - A problem of partitioning a finite sequence of points in Euclidean space into two subsequences (clusters) maximizing the size of the first cluster subject to two constraints is considered. The first constraint deals with every two consecutive indices of elements of the first cluster: the difference between them is bounded from above and below by some constants. The second one restricts the value of a quadratic clustering function that is the sum of the intracluster sums over both clusters. The intracluster sum is the sum of squared distances between cluster elements and the cluster center. The center of the first cluster is unknown and determined as the centroid (i.e. as the mean value of its elements), while the center of the second one is zero. The strong NP-hardness of the problem is shown and an exact algorithm is suggested for the case of integer coordinates of input points. If the space dimension is bounded by some constant this algorithm runs in a pseudopolynomial time.

KW - 2-partition

KW - Euclidean space

KW - Exact algorithm

KW - Fixed space dimension

KW - Integer coordinates

KW - Longest subsequence

KW - NP-hard problem

KW - Pseudopolynomial running time

KW - Quadratic variance

KW - Sequence

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

U2 - 10.1007/978-3-030-10934-9_10

DO - 10.1007/978-3-030-10934-9_10

M3 - Conference contribution

AN - SCOPUS:85061210935

SN - 9783030109332

T3 - Communications in Computer and Information Science

SP - 131

EP - 143

BT - Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers

A2 - Kochetov, Yury

A2 - Khachay, Michael

A2 - Evtushenko, Yury

A2 - Malkova, Vlasta

A2 - Posypkin, Mikhail

A2 - Jacimovic, Milojica

PB - Springer-Verlag GmbH and Co. KG

T2 - 9th International Conference on Optimization and Applications, OPTIMA 2018

Y2 - 1 October 2018 through 5 October 2018

ER -

ID: 18503704