Standard

The Problem K-Means and Given J-Centers : Polynomial Solvability in One Dimension. / Kel’manov, Alexander; Khandeev, Vladimir.

Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. ed. / Igor Bykadorov; Vitaly Strusevich; Tatiana Tchemisova. Springer International Publishing AG, 2019. p. 207-216 (Communications in Computer and Information Science; Vol. 1090 CCIS).

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

Harvard

Kel’manov, A & Khandeev, V 2019, The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension. in I Bykadorov, V Strusevich & T Tchemisova (eds), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. Communications in Computer and Information Science, vol. 1090 CCIS, Springer International Publishing AG, pp. 207-216, 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019, Ekaterinburg, Russian Federation, 08.07.2019. https://doi.org/10.1007/978-3-030-33394-2_16

APA

Kel’manov, A., & Khandeev, V. (2019). The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension. In I. Bykadorov, V. Strusevich, & T. Tchemisova (Eds.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers (pp. 207-216). (Communications in Computer and Information Science; Vol. 1090 CCIS). Springer International Publishing AG. https://doi.org/10.1007/978-3-030-33394-2_16

Vancouver

Kel’manov A, Khandeev V. The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension. In Bykadorov I, Strusevich V, Tchemisova T, editors, Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. Springer International Publishing AG. 2019. p. 207-216. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-33394-2_16

Author

Kel’manov, Alexander ; Khandeev, Vladimir. / The Problem K-Means and Given J-Centers : Polynomial Solvability in One Dimension. Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. editor / Igor Bykadorov ; Vitaly Strusevich ; Tatiana Tchemisova. Springer International Publishing AG, 2019. pp. 207-216 (Communications in Computer and Information Science).

BibTeX

@inproceedings{67ae48989dec41a7a9d5c77c2503f620,
title = "The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension",
abstract = "We consider a 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 one part of the clusters are given as an input, while the centers of the other part of the clusters are defined as centroids (geometrical centers). It is known that in the general case this problem is strongly NP-hard. We prove constructively that the one-dimensional case of this problem is solvable in polynomial time. This result is based, first, on the proved properties of the problem optimal solution and, second, on the justified dynamic programming scheme.",
keywords = "Euclidean space, Minimum sum-of-squares clustering, One-dimensional case, Polynomial-time algorithm, Strongly NP-hard problem",
author = "Alexander Kel{\textquoteright}manov and Vladimir Khandeev",
note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-33394-2_16",
language = "English",
isbn = "9783030333935",
series = "Communications in Computer and Information Science",
publisher = "Springer International Publishing AG",
pages = "207--216",
editor = "Igor Bykadorov and Vitaly Strusevich and Tatiana Tchemisova",
booktitle = "Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers",
address = "Switzerland",

}

RIS

TY - GEN

T1 - The Problem K-Means and Given J-Centers

T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019

AU - Kel’manov, Alexander

AU - Khandeev, Vladimir

N1 - Publisher Copyright: © 2019, Springer Nature Switzerland AG.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We consider a 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 one part of the clusters are given as an input, while the centers of the other part of the clusters are defined as centroids (geometrical centers). It is known that in the general case this problem is strongly NP-hard. We prove constructively that the one-dimensional case of this problem is solvable in polynomial time. This result is based, first, on the proved properties of the problem optimal solution and, second, on the justified dynamic programming scheme.

AB - We consider a 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 one part of the clusters are given as an input, while the centers of the other part of the clusters are defined as centroids (geometrical centers). It is known that in the general case this problem is strongly NP-hard. We prove constructively that the one-dimensional case of this problem is solvable in polynomial time. This result is based, first, on the proved properties of the problem optimal solution and, second, on the justified dynamic programming scheme.

KW - Euclidean space

KW - Minimum sum-of-squares clustering

KW - One-dimensional case

KW - Polynomial-time algorithm

KW - Strongly NP-hard problem

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

U2 - 10.1007/978-3-030-33394-2_16

DO - 10.1007/978-3-030-33394-2_16

M3 - Conference contribution

AN - SCOPUS:85076160194

SN - 9783030333935

T3 - Communications in Computer and Information Science

SP - 207

EP - 216

BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers

A2 - Bykadorov, Igor

A2 - Strusevich, Vitaly

A2 - Tchemisova, Tatiana

PB - Springer International Publishing AG

Y2 - 8 July 2019 through 12 July 2019

ER -

ID: 22995093