Standard

NP-Hardness of balanced minimum sum-of-squares clustering. / Pyatkin, Artem; Aloise, Daniel; Mladenović, Nenad.

в: Pattern Recognition Letters, Том 97, 01.10.2017, стр. 44-45.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Pyatkin, A, Aloise, D & Mladenović, N 2017, 'NP-Hardness of balanced minimum sum-of-squares clustering', Pattern Recognition Letters, Том. 97, стр. 44-45. https://doi.org/10.1016/j.patrec.2017.05.033

APA

Pyatkin, A., Aloise, D., & Mladenović, N. (2017). NP-Hardness of balanced minimum sum-of-squares clustering. Pattern Recognition Letters, 97, 44-45. https://doi.org/10.1016/j.patrec.2017.05.033

Vancouver

Pyatkin A, Aloise D, Mladenović N. NP-Hardness of balanced minimum sum-of-squares clustering. Pattern Recognition Letters. 2017 окт. 1;97:44-45. doi: 10.1016/j.patrec.2017.05.033

Author

Pyatkin, Artem ; Aloise, Daniel ; Mladenović, Nenad. / NP-Hardness of balanced minimum sum-of-squares clustering. в: Pattern Recognition Letters. 2017 ; Том 97. стр. 44-45.

BibTeX

@article{bc0b727467594e9489dbf6de3890bc2d,
title = "NP-Hardness of balanced minimum sum-of-squares clustering",
abstract = "The balanced clustering problem consists of partitioning a set of n objects into K equal-sized clusters as long as n is a multiple of K. A popular clustering criterion when the objects are points of a q-dimensional space is the minimum sum of squared distances from each point to the centroid of the cluster to which it belongs. We show in this paper that this problem is NP-hard in general dimension already for triplets, i.e., when n/K=3.",
keywords = "Balanced clustering, Complexity, Sum-of-squares, COMPLEXITY",
author = "Artem Pyatkin and Daniel Aloise and Nenad Mladenovi{\'c}",
note = "Funding Information: This research was partially supported by RFBR, projects 16-07-00168 and 15-01-00462, by RSF grant 14-41-00039, and by CNPq/Brazil grants 308887/2014-0 and 400350/2014-9. Publisher Copyright: {\textcopyright} 2017 Elsevier B.V. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.",
year = "2017",
month = oct,
day = "1",
doi = "10.1016/j.patrec.2017.05.033",
language = "English",
volume = "97",
pages = "44--45",
journal = "Pattern Recognition Letters",
issn = "0167-8655",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - NP-Hardness of balanced minimum sum-of-squares clustering

AU - Pyatkin, Artem

AU - Aloise, Daniel

AU - Mladenović, Nenad

N1 - Funding Information: This research was partially supported by RFBR, projects 16-07-00168 and 15-01-00462, by RSF grant 14-41-00039, and by CNPq/Brazil grants 308887/2014-0 and 400350/2014-9. Publisher Copyright: © 2017 Elsevier B.V. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2017/10/1

Y1 - 2017/10/1

N2 - The balanced clustering problem consists of partitioning a set of n objects into K equal-sized clusters as long as n is a multiple of K. A popular clustering criterion when the objects are points of a q-dimensional space is the minimum sum of squared distances from each point to the centroid of the cluster to which it belongs. We show in this paper that this problem is NP-hard in general dimension already for triplets, i.e., when n/K=3.

AB - The balanced clustering problem consists of partitioning a set of n objects into K equal-sized clusters as long as n is a multiple of K. A popular clustering criterion when the objects are points of a q-dimensional space is the minimum sum of squared distances from each point to the centroid of the cluster to which it belongs. We show in this paper that this problem is NP-hard in general dimension already for triplets, i.e., when n/K=3.

KW - Balanced clustering

KW - Complexity

KW - Sum-of-squares

KW - COMPLEXITY

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

U2 - 10.1016/j.patrec.2017.05.033

DO - 10.1016/j.patrec.2017.05.033

M3 - Article

AN - SCOPUS:85021763075

VL - 97

SP - 44

EP - 45

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

SN - 0167-8655

ER -

ID: 9033176