A faster algorithm for the two cluster partitioning problem

• Francisco-Javier Soto ^[1] ; Ana I. Gómez ^[2] ; Domingo Gómez-Pérez ^[1]
  1. [1] Universidad de Cantabria

     Universidad de Cantabria

     Santander, España

     
  2. [2] Universidad Rey Juan Carlos

     Universidad Rey Juan Carlos

     Madrid, España

     
• Localización: Discrete Mathematics Days 2022 / Luis Felipe Tabera Alonso (ed. lit.) , 2022, ISBN 978-84-19024-02-2, págs. 255-260
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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.