@online{Herold2410.24104,
TITLE = {Clustering to Minimize Cluster-Aware Norm Objectives},
AUTHOR = {Herold, Martin G. and Kipouridis, Evangelos and Spoerhase, Joachim},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2410.24104},
EPRINT = {2410.24104},
EPRINTTYPE = {arXiv},
YEAR = {2024},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We initiate the study of the following general clustering problem. We seek to<br>partition a given set $P$ of data points into $k$ clusters by finding a set $X$<br>of $k$ centers and assigning each data point to one of the centers. The cost of<br>a cluster, represented by a center $x\in X$, is a monotone, symmetric norm $f$<br>(inner norm) of the vector of distances of points assigned to $x$. The goal is<br>to minimize a norm $g$ (outer norm) of the vector of cluster costs. This<br>problem, which we call $(f,g)$-Clustering, generalizes many fundamental<br>clustering problems such as $k$-Center, $k$-Median , Min-Sum of Radii, and<br>Min-Load $k$-Clustering . A recent line of research (Chakrabarty, Swamy<br>[STOC'19]) studies norm objectives that are oblivious to the cluster structure<br>such as $k$-Median and $k$-Center. In contrast, our problem models<br>cluster-aware objectives including Min-Sum of Radii and Min-Load<br>$k$-Clustering.<br> Our main results are as follows. First, we design a constant-factor<br>approximation algorithm for $(\textsf{top}_\ell,\mathcal{L}_1)$-Clustering<br>where the inner norm ($\textsf{top}_\ell$) sums over the $\ell$ largest<br>distances. Second, we design a constant-factor approximation\ for<br>$(\mathcal{L}_\infty,\textsf{Ord})$-Clustering where the outer norm is a convex<br>combination of $\textsf{top}_\ell$ norms (ordered weighted norm).<br>},
}