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

Alexander Kel’manov; Sergey Khamidullin; Vladimir Khandeev; Artem Pyatkin

doi:10.1007/978-3-030-10934-9_10

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

Alexander Kel’manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin

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

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.

Original language	English
Title of host publication	Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
Editors	Yury Kochetov, Michael Khachay, Yury Evtushenko, Vlasta Malkova, Mikhail Posypkin, Milojica Jacimovic
Publisher	Springer-Verlag GmbH and Co. KG
Pages	131-143
Number of pages	13
ISBN (Print)	9783030109332
DOIs	https://doi.org/10.1007/978-3-030-10934-9_10
Publication status	Published - 1 Jan 2019
Event	9th International Conference on Optimization and Applications, OPTIMA 2018 - Petrovac, Montenegro Duration: 1 Oct 2018 → 5 Oct 2018

Publication series

Name	Communications in Computer and Information Science
Volume	974
ISSN (Print)	1865-0929

Conference

Conference	9th International Conference on Optimization and Applications, OPTIMA 2018
Country/Territory	Montenegro
City	Petrovac
Period	01.10.2018 → 05.10.2018

Keywords

2-partition
Euclidean space
Exact algorithm
Fixed space dimension
Integer coordinates
Longest subsequence
NP-hard problem
Pseudopolynomial running time
Quadratic variance
Sequence

Access to Document

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

Cite this

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

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).

@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",

}

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

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

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 -

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). https://doi.org/10.1007/978-3-030-10934-9_10

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this