# A Broader View on Clustering under Cluster-Aware Norm Objectives

arXiv: https://arxiv.org/abs/2512.06211 · HTML: https://mlsanity.com/paper/2512.06211/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 5 Dec 2025.

## Builds on (most cited first, 14 of 14)

- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Approximation Algorithms for Minimum Norm and Ordered Optimization Problems](https://mlsanity.com/paper/1811.05022/) (2018)
- [Constant-Factor Approximation for Ordered k-Median](https://mlsanity.com/paper/1711.01972/) (2017)
- [Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers](https://mlsanity.com/paper/1608.01700/) (2016)
- [Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median](https://mlsanity.com/paper/1711.08715/) (2017)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Submodular Norms with Applications To Online Facility Location and Stochastic Probing](https://mlsanity.com/paper/2310.04548/) (2023)
- [Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization](https://mlsanity.com/paper/2010.05127/) (2020)
- [Generalized Unrelated Machine Scheduling Problem](https://mlsanity.com/paper/2202.06292/) (2022)
- [Improved Bi-point Rounding Algorithms and a Golden Barrier for k-Median](https://mlsanity.com/paper/2210.13395/) (2022)
- [An O(loglog n)-Approximation for Submodular Facility Location](https://mlsanity.com/paper/2211.05474/) (2022)
- [Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii](https://mlsanity.com/paper/2412.16327/) (2024)
- [Clustering to Minimize Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2410.24104/) (2024)

## Abstract (arXiv)

We revisit the (f,g)-clustering problem that we introduced in a recent work [SODA'25], and which subsumes fundamental clustering problems such as k-Center, k-Median, Min-Sum of Radii, and Min-Load k-Clustering. This problem assigns each of the k clusters a cost determined by the monotone, symmetric norm f applied to the vector distances in the cluster, and aims at minimizing the norm g applied to the vector of cluster costs. Previously, we focused on certain special cases 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 O(log2 n)-approximation algorithm for (f, L1)-clustering for any f. This improves upon our previous widetildeO(√n)-approximation. Second, we provide an O(k)-approximation for the general (f,g)-clustering problem, which improves upon our previous widetildeO(√kn)-approximation algorithm and matches the best-known upper bound for Min-Load k-Clustering. We then design an approximation algorithm for (f,g)-clustering that interpolates, up to polylog factors, between the best known bounds for k-Center, k-Median, Min-Sum of Radii, Min-Load k-Clustering, (Top, L1)-clustering, and (L∞,g)-clustering based on a newly defined parameter of f and g.