Resumen de A faster algorithm for the two cluster partitioning problem

Francisco Javier Soto, Ana I. Gómez, Domingo Gómez Pérez

• Clustering (partitioning a set into different subsets) are among the most widely usedtype of algorithms for unstructured data and often means solving a combinatorial problemof finding the minimum of an objective function. The most popular clustering algorithm inpractice is Lloyd’s heuristic approximation algorithm to the k-means optimum centroids. Acrucial issue of this approach is that there is only a probabilistic guarantee regarding thegoodness of the solution. Indeed, it is possible to construct datasets where Lloyd’s heuristicapproximation algorithm only finds local minimums. A challenging problem is finding theglobal optimum for any given dataset. Although this problem is NP-hard, new algorithmsfor finding optimal clustering offer many benefits such as the research of new heuristicalgorithms. This work analyses possible improvements for solving this problem, focusing onoptimizing the global searches with branch-and-bound techniques. The numerical resultsshow a promising computational advantage for the case of the partitioning of two sets overprevious proposals.