Standard

On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. / Kel’manov, Alexander; Khandeev, Vladimir.

Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. ed. / Nikolaos F. Matsatsinis; Yannis Marinakis; Panos Pardalos. Springer Gabler, 2020. p. 46-52 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11968 LNCS).

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

Harvard

Kel’manov, A & Khandeev, V 2020, On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. in NF Matsatsinis, Y Marinakis & P Pardalos (eds), Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11968 LNCS, Springer Gabler, pp. 46-52, 13th International Conference on Learning and Intelligent Optimization, LION 13, Chania, Greece, 27.05.2019. https://doi.org/10.1007/978-3-030-38629-0_4

APA

Kel’manov, A., & Khandeev, V. (2020). On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. In N. F. Matsatsinis, Y. Marinakis, & P. Pardalos (Eds.), Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers (pp. 46-52). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11968 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-38629-0_4

Vancouver

Kel’manov A, Khandeev V. On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. In Matsatsinis NF, Marinakis Y, Pardalos P, editors, Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. Springer Gabler. 2020. p. 46-52. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-38629-0_4

Author

Kel’manov, Alexander ; Khandeev, Vladimir. / On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers. editor / Nikolaos F. Matsatsinis ; Yannis Marinakis ; Panos Pardalos. Springer Gabler, 2020. pp. 46-52 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{c7ee023902f24abb9f153c471ea476ab,
title = "On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line",
abstract = "We consider one problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum over all clusters of the intracluster sums of the squared distances between clusters elements and their centers. The centers of some clusters are given as an input, while the other centers are unknown and defined as centroids (geometrical centers). It is known that the general case of the problem is strongly NP-hard. We show that there exists an exact polynomial algorithm for the one-dimensional case of the problem.",
keywords = "Euclidean space, Minimum Sum-of-Squares Clustering, NP-hard problem, One-dimensional case, Polynomial solvability",
author = "Alexander Kel{\textquoteright}manov and Vladimir Khandeev",
note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 13th International Conference on Learning and Intelligent Optimization, LION 13 ; Conference date: 27-05-2019 Through 31-05-2019",
year = "2020",
month = jan,
day = "22",
doi = "10.1007/978-3-030-38629-0_4",
language = "English",
isbn = "9783030386283",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Gabler",
pages = "46--52",
editor = "Matsatsinis, {Nikolaos F.} and Yannis Marinakis and Panos Pardalos",
booktitle = "Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers",
address = "Germany",

}

RIS

TY - GEN

T1 - On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line

AU - Kel’manov, Alexander

AU - Khandeev, Vladimir

N1 - Publisher Copyright: © 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/1/22

Y1 - 2020/1/22

N2 - We consider one problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum over all clusters of the intracluster sums of the squared distances between clusters elements and their centers. The centers of some clusters are given as an input, while the other centers are unknown and defined as centroids (geometrical centers). It is known that the general case of the problem is strongly NP-hard. We show that there exists an exact polynomial algorithm for the one-dimensional case of the problem.

AB - We consider one problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum over all clusters of the intracluster sums of the squared distances between clusters elements and their centers. The centers of some clusters are given as an input, while the other centers are unknown and defined as centroids (geometrical centers). It is known that the general case of the problem is strongly NP-hard. We show that there exists an exact polynomial algorithm for the one-dimensional case of the problem.

KW - Euclidean space

KW - Minimum Sum-of-Squares Clustering

KW - NP-hard problem

KW - One-dimensional case

KW - Polynomial solvability

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

U2 - 10.1007/978-3-030-38629-0_4

DO - 10.1007/978-3-030-38629-0_4

M3 - Conference contribution

AN - SCOPUS:85082389518

SN - 9783030386283

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

SP - 46

EP - 52

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

A2 - Matsatsinis, Nikolaos F.

A2 - Marinakis, Yannis

A2 - Pardalos, Panos

PB - Springer Gabler

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

Y2 - 27 May 2019 through 31 May 2019

ER -

ID: 23877324