# Clustering to Minimize Cluster-Aware Norm Objectives

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 38 references that are in the map.
- First posted on arXiv 31 Oct 2024.

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

- [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)
- [The Non-Uniform k-Center Problem](https://mlsanity.com/paper/1605.03692/) (2016)
- [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)
- [An O(loglog n)-Approximation for Submodular Facility Location](https://mlsanity.com/paper/2211.05474/) (2022)

## Built on by (most cited first, 1 of 1)

- [A Broader View on Clustering under Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2512.06211/) (2025)

## Abstract (arXiv)

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∈ X, is a monotone, symmetric norm f (inner norm) of the vector of distances of points assigned to x. The goal is to minimize a norm g (outer norm) of the vector of cluster costs. This problem, which we call (f,g)-Clustering, generalizes many fundamental clustering problems such as k-Center, k-Median , Min-Sum of Radii, and Min-Load k-Clustering . A recent line of research (Chakrabarty, Swamy [STOC'19]) 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 (textsftopℓ,L1)-Clustering where the inner norm (textsftopℓ) sums over the ℓ largest distances. Second, we design a constant-factor approximation for (L_∞,textsfOrd)-Clustering where the outer norm is a convex combination of textsftopℓ norms (ordered weighted norm).