A Broader View on Clustering under Cluster-Aware Norm Objectives

We revisit the pf, gq-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., 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).

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.

In this work, we provide a clearer picture of the approximability of these more general settings. First, we design an Oplog 2 nq-approximation algorithm for pSym, L 1 q-Clustering, that is, when the inner norm is an arbitrary monotone, symmetric norm. This improves upon our previous r Op ? nq-approximation even for the special case of ordered weighted norms. Second, we provide an Opkq-approximation for the general pSym, Symq-Clustering problem, which improves upon our previous r Op ? knq-approximation algorithm and matches the best-known upper bound for Min-Load k-Clustering.

We then combine our new and previous algorithms to interpolate between the above four basic objectives. Specifically, we obtain an upper approximability bound of r Opmintn χ f , k 1´χg uq for pf, gq-Clustering under arbitrary monotone, symmetric norms f, g. Here, for any such norm h : R d Ñ R ě0 , the parameter χ h " plog hp1, 1, . . . , 1q ´log hp1, 0, . . . , 0qq log d, which we call attenuation, maps any monotone, symmetric norm onto a r0, 1s-spectrum between the extremes L 8 (χ h " 0) and L 1 (χ h " 1). This upper bound recovers-up to poly-log factors-the best existing approximation algorithms for k-Center, k-Median, Min-Sum of Radii, Min-Load k-Clustering, pTop, L 1 q-Clustering, and pL 8 , Symq-Clustering. We observe that a hypothetical opkq-hardness of approximating certain "compact" instances for Min-Load k-Clustering would imply polynomial inapproximability bounds for pf, gq-Clustering for any pair of norms f, g with χ g ă χ f contrasting the existing Op1q-approximation algorithms for pk, zq-Clustering (i.e., pL z , L z q-Clustering) where χ f " χ g .

• Martin Herold is funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) -Project number 399223600. We are grateful to an anonymous reviewer for making concrete suggestions how to substantially simplify the proof of Lemma 30.