Clustering to Minimize Cluster-Aware Norm Objectives
Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase · Society for Industrial and Applied Mathematics eBooks · 2025
We initiate the study of the following general clustering problem. We seek to partition a given set P of data points into k clusters by finding a set X of k centers and assigning each data point to one of the centers. The cost of a cluster, represented by a center x ∊ X, is a monotone, symmetric norm f (called inner norm) of the vector of distances of points assigned to x. The goal is to minimize a norm g (called outer norm) of the vector of cluster costs. This problem, which we call (f, g )-Clustering, generalizes many fundamental clustering problems such as k-Center (i.e., (𝓛∞, 𝓛∞)-Clustering), k-Median (i.e., (𝓛1, 𝓛1)-Clustering), Min-Sum of Radii (i.e., (𝓛∞, 𝓛1)-Clustering), and Min-Load k-Clustering (i.e., (𝓛1, L∞)-Clustering). A recent line of research (Byrka et al. [STOC’18], Chakrabarty, Swamy [ICALP’18, STOC’19], and Abbasi et al. [FOCS’23]) studies norm objectives that are oblivious to the cluster structure such as k-Median and k-Center. In contrast, our problem models cluster-aware objectives including Min-Sum of Radii and Min-Load k-Clustering.