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

Standard

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

In: Doklady Mathematics, Vol. 100, No. 1, 01.07.2019, p. 339-342.

Research output: Contribution to journal › Article › peer-review

Harvard

Kel’manov, AV & Khandeev, VI 2019, 'On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line', Doklady Mathematics, vol. 100, no. 1, pp. 339-342. https://doi.org/10.1134/S1064562419040057

APA

Kel’manov, A. V., & Khandeev, V. I. (2019). On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. Doklady Mathematics, 100(1), 339-342. https://doi.org/10.1134/S1064562419040057

Vancouver

Kel’manov AV, Khandeev VI. On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. Doklady Mathematics. 2019 Jul 1;100(1):339-342. doi: 10.1134/S1064562419040057

Author

Kel’manov, A. V. ; Khandeev, V. I. / On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. In: Doklady Mathematics. 2019 ; Vol. 100, No. 1. pp. 339-342.

BibTeX

@article{ccb8939ad6a84a409f28b6c5cf70c3c4,

title = "On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line",

abstract = "We consider the 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 cluster elements and their centers. The centers of some clusters are given as input, while the other centers are defined as centroids (geometric centers). It is well known that the general case of the problem is strongly NP-hard. In this paper, we have shown that there exists an exact polynomial-time algorithm for the one-dimensional case of the problem.",

author = "Kel{\textquoteright}manov, {A. V.} and Khandeev, {V. I.}",

note = "Publisher Copyright: {\textcopyright} 2019, Pleiades Publishing, Ltd.",

year = "2019",

month = jul,

day = "1",

doi = "10.1134/S1064562419040057",

language = "English",

volume = "100",

pages = "339--342",

journal = "Doklady Mathematics",

issn = "1064-5624",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "1",

}

RIS

TY - JOUR

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

AU - Kel’manov, A. V.

AU - Khandeev, V. I.

PY - 2019/7/1

Y1 - 2019/7/1

N2 - We consider the 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 cluster elements and their centers. The centers of some clusters are given as input, while the other centers are defined as centroids (geometric centers). It is well known that the general case of the problem is strongly NP-hard. In this paper, we have shown that there exists an exact polynomial-time algorithm for the one-dimensional case of the problem.

AB - We consider the 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 cluster elements and their centers. The centers of some clusters are given as input, while the other centers are defined as centroids (geometric centers). It is well known that the general case of the problem is strongly NP-hard. In this paper, we have shown that there exists an exact polynomial-time algorithm for the one-dimensional case of the problem.

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

U2 - 10.1134/S1064562419040057

DO - 10.1134/S1064562419040057

M3 - Article

AN - SCOPUS:85073875419

VL - 100

SP - 339

EP - 342

JO - Doklady Mathematics

JF - Doklady Mathematics

SN - 1064-5624

IS - 1

ER -

ID: 22319319