Clustering to Minimize Cluster-Aware Norm Objectives

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 $(\textsf{top}_\ell,\mathcal{L}_{1})$-Clustering where the inner norm ($\textsf{top}_\ell$) sums over the $\ell$ 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 $(\mathcal{L}_{\infty},\textsf{Ord})$-Clustering where the outer
norm is a convex combination of $\textsf{top}_\ell$ 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
$(\mathcal{L}_{1},\mathcal{L}_{\infty})$-Clustering (Min-Load $k$-Clustering) seems challenging because even an $o(k)$-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 $(\textsf{top}_\ell,\mathcal{L}_{1})$-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 of Radii Objective (Charikar and Panigrahi [STOC'01] and Ahmadian and Swamy [ICALP'16]).