Show simple item record

dc.contributor.authorTirnauca, Cristina 
dc.contributor.authorGómez Pérez, Domingo 
dc.contributor.authorBalcázar, José Luis
dc.contributor.authorMontaña Arnaiz, José Luis 
dc.contributor.otherUniversidad de Cantabriaes_ES
dc.description.abstractAbstract: We study the problem of finding an optimum clustering, a problem known to be NP-hard. Existing literature contains algorithms running in time proportional to the number of points raised to a power that depends on the dimensionality and on the number of clusters. Published validations of some of these algorithms are unfortunately incomplete; besides, the constant factors (with respect to the number of points) in their running time bounds have seen several published important improvements but are still huge, exponential on the dimension and on the number of clusters, making the corresponding algorithms fully impractical. We provide a new algorithm, with its corresponding complexity-theoretic analysis. It reduces both the exponent and the constant factor, to the extent that it becomes feasible for relevant particular cases. Additionally, it parallelizes extremely well, so that its implementation on current high-performance hardware is quite straightforward. Our proposal opens the door to potential improvements along a research line that had no practical significance so far; besides, a long but single-shot run of our algorithm allows one to identify absolutely optimum solutions for benchmark problems, whereby alternative heuristic proposals can evaluate the goodness of their solutions and the precise price paid for their faster running times.es_ES
dc.format.extent39 p.es_ES
dc.rights© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 licensees_ES
dc.sourceInformation Sciences, Volumes 439-440, May 2018, Pages 79-94es_ES
dc.titleGlobal optimality in k-means clusteringes_ES

Files in this item


This item appears in the following Collection(s)

Show simple item record

© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 licenseExcept where otherwise noted, this item's license is described as © 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license