Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem

Standard

Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem. / Kel’manov, A. V.; Khandeev, V. I.

In: Computational Mathematics and Mathematical Physics, Vol. 59, No. 9, 01.09.2019, p. 1553-1561.

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

Harvard

Kel’manov, AV & Khandeev, VI 2019, 'Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem', Computational Mathematics and Mathematical Physics, vol. 59, no. 9, pp. 1553-1561. https://doi.org/10.1134/S0965542519090112

APA

Kel’manov, A. V., & Khandeev, V. I. (2019). Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem. Computational Mathematics and Mathematical Physics, 59(9), 1553-1561. https://doi.org/10.1134/S0965542519090112

Vancouver

Kel’manov AV, Khandeev VI. Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem. Computational Mathematics and Mathematical Physics. 2019 Sept 1;59(9):1553-1561. doi: 10.1134/S0965542519090112

Author

Kel’manov, A. V. ; Khandeev, V. I. / Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem. In: Computational Mathematics and Mathematical Physics. 2019 ; Vol. 59, No. 9. pp. 1553-1561.

BibTeX

@article{e958be6da4b94e43b9678a88c8db709c,

title = "Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem",

abstract = "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 of the clusters are given as an input, while the centers of the others are determined as centroids (geometric 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.",

keywords = "clustering, Euclidean space, minimum sum-of-squares, one-dimensional case, partitioning, polynomial-time solvability, strongly NP-hard problem, COMPLEXITY",

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

year = "2019",

month = sep,

day = "1",

doi = "10.1134/S0965542519090112",

language = "English",

volume = "59",

pages = "1553--1561",

journal = "Computational Mathematics and Mathematical Physics",

issn = "0965-5425",

publisher = "PLEIADES PUBLISHING INC",

number = "9",

}

RIS

TY - JOUR

T1 - Polynomial-Time Solvability of the One-Dimensional Case of an NP-Hard Clustering Problem

AU - Kel’manov, A. V.

AU - Khandeev, V. I.

PY - 2019/9/1

Y1 - 2019/9/1

N2 - 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 of the clusters are given as an input, while the centers of the others are determined as centroids (geometric 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.

AB - 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 of the clusters are given as an input, while the centers of the others are determined as centroids (geometric 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.

KW - clustering

KW - Euclidean space

KW - minimum sum-of-squares

KW - one-dimensional case

KW - partitioning

KW - polynomial-time solvability

KW - strongly NP-hard problem

KW - COMPLEXITY

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

U2 - 10.1134/S0965542519090112

DO - 10.1134/S0965542519090112

M3 - Article

AN - SCOPUS:85073559723

VL - 59

SP - 1553

EP - 1561

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 9

ER -

ID: 21938810