2020/12/10 by Steffen Borgwardt, Borgwardt, Steffen, Felix Happach +3
Business, Management and Accounting · Computer Science · Mathematics · #51M20 #62H30 #90C05 #90C31 #90C90 #Advanced Clustering Algorithms Research #Data Management and Algorithms #FOS: Mathematics #Facility Location and Emergency Management #Optimization and Control (math.OC) #math.OC #msc:51M20 #msc:62H30 #msc:90C05 #msc:90C31 #msc:90C90
paper · pdf · doi:10.48550/arxiv.2012.05929
openalex publication_date 2020/12/10 · arxiv created 2022/01/24 · arxiv updated 2022/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The separability of clusters is one of the most desired properties in clustering. There is a wide range of settings in which different clusterings of the same data set appear. We are interested in applications where there is a need for an explicit, gradual transition of one separable clustering into another one. This transition should be a sequence of simple, natural steps that upholds separability of the clusters throughout. We design an algorithm for such a transition. We exploit the intimate connection of separability and linear programming over bounded-shape partition and transportation polytopes: separable clusterings lie on the boundary of partition polytopes, form a subset of the vertices of the corresponding transportation polytopes, and circuits of both polytopes are readily interpreted as sequential or cyclical exchanges of items between clusters. This allows for a natural approach to achieve the desired transition through a combination of two walks: an edge walk between two so-called radial clusterings in a transportation polytope, computed through an adaptation of classical tools of sensitivity analysis and parametric programming; and a walk from a separable clustering to a corresponding radial clustering, computed through a tailored, iterative routine updating cluster sizes and re-optimizing the cluster assignment of items.