A bisection method for solving distance-based clustering problems globally

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