Clustering to Minimize Cluster-Aware Norm Objectives

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 P 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 pf, gq-Clustering, generalizes many fundamental clustering problems such as k-Center (i.e., pL 8 , L 8 q-Clustering), k-Median (i.e., pL 1 , L 1 q-Clustering), Min-Sum of Radii (i.e., pL 8 , L 1 q-Clustering), and Min-Load k-Clustering (i.e., pL 1 , L 8 q-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.

Our main results are as follows. First, we design a constant-factor approximation algorithm for ptop ℓ , L 1 q-Clustering where the inner norm (top ℓ ) sums over the ℓ largest distances. This unifies (up to constant factors) the best known results for k-Median and Min-Sum of Radii. Second, we design a constant-factor approximation for pL 8 , Ordq-Clustering where the outer norm is a convex combination of top ℓ norms (ordered weighted norm). This generalizes known results for k-Center and Min-Sum of Radii. Obtaining a constant-factor approximation for more general settings that include pL 1 , L 8 q-Clustering (Min-Load k-Clustering) seems challenging because even an opkq-approximation is unknown for this problem. We can still use our two main results to obtain first (although non-constant) approximations for these problems including general monotone, symmetric norms.

Our algorithm for ptop ℓ , L 1 q-Clustering relies on a reduction to a novel generalization of k-Median, which we call Ball k-Median. In this problem, we aim at selecting k balls (rather than k centers) and pay for connecting the points to these balls as well as for the (scaled) radii of the balls. To obtain a constant-factor approximation for this problem we unify various algorithmic techniques originally designed for the cluster-oblivious k-Median objective (Jain and Vazirani [JACM 2001], Li and Svensson [STOC'13]) and for the cluster-aware Min-Sum Radii Objective (Charikar and Panigrahi [STOC'01] and Ahmadian and Swamy [ICALP'16]).