2024/10/31 by Herold, Martin G., Kipouridis, Evangelos, Spoerhase, Joachim · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2410.24104
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 (inner norm) of the vector of distances of points assigned to x. The goal is to minimize a norm g (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, k-Median , Min-Sum of Radii, and Min-Load k-Clustering . A recent line of research (Chakrabarty, Swamy [STOC'19]) 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. Our main results are as follows. First, we design a constant-factor approximation algorithm for (\textsftop_ℓ,L1)-Clustering where the inner norm (\textsftop_ℓ) sums over the ℓ largest distances. Second, we design a constant-factor approximation for (L_∞,\textsfOrd)-Clustering where the outer norm is a convex combination of \textsftop_ℓ norms (ordered weighted norm).