A bisection method for solving distance-based clustering problems globally

Peter Kirst (), Tomáš Bajbar () and Mario Merkel ()
Additional contact information
Peter Kirst: Wageningen University and Research
Tomáš Bajbar: Karlsruhe Institute of Technology (KIT)
Mario Merkel: Karlsruhe Institute of Technology (KIT)

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2025, vol. 33, issue 3, No 1, 437-469

Abstract: Abstract In this article, we consider distance-based clustering problems. In contrast to many approaches, we use the maximum norm instead of the more commonly used Euclidean norm to measure distances. This problem is nonsmooth and non-convex and, thus, difficult to solve to global optimality using standard approaches, which is common in cluster analysis. Therefore, we reformulate this continuous problem in light of graph-theoretical instances which enables us to construct a bisection algorithm converging to the globally minimal value of the original clustering problem by establishing valid upper and lower bounding procedures. Our numerical results indicate that our method performs well on data sets exhibiting clear cluster-pattern structure even for bigger data instances while still guaranteeing the global optimality of the computed solution. We compare our approach with the classical k-means algorithm and also discuss the limits and challenges of the proposed procedure.

Keywords: Clustering problem; Global optimization; Maximal clique; Bisection method; k-means problem; 90C30; 90C26; 90C35 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-024-00684-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:33:y:2025:i:3:d:10.1007_s11750-024-00684-w

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-024-00684-w

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().