A Broader View on Clustering under Cluster-Aware Norm Objectives

We revisit the (\(f,q\))-Clustering problem that we introduced in a recent work [SODA’25]. Here, \(f\) and \(g\) are symmetric, monotone norms called inner and outer norms, respectively. The task is to partition a given set of points in a metric space into \(k\) clusters each represented by a cluster center. Each cluster is assigned a cluster cost, determined by the norm \(f\) applied to the vector of point-center distances in the cluster. The goal is to minimize the value of the norm \(g\) when applied to the vector of cluster costs. This problem subsumes fundamental clustering problems such as \(k\)-Center (i.e., \(\mathcal L_\infty, \mathcal L_\infty\)-Clustering), \(k\)-Median (i.e., \(\mathcal L_1, \mathcal L_1\)-Clustering), Min-Sum of Radii (i.e., \(\mathcal L_\infty, \mathcal L_1\)-Clustering), and Min-Load \(k\)-Clustering (i.e., \(\mathcal L_1, \mathcal L_\infty\)-Clustering). In our previous work, we focused on certain special cases of this problem for which we designed constant-factor approximation algorithms. Our bounds for more general settings left, however, large gaps to the known bounds for the basic problems they capture.