{"ID":6620518,"CreatedAt":"2026-07-15T01:01:48.440468303Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.12421","arxiv_id":"2607.12421","title":"Adaptive Sampling for Minimum-Norm $k$-Clustering","abstract":"In $k$-clustering problems, we are given a metric space $(\\mathcal{C}, d)$, and must choose a set $S$ of $k$ centers to open. Each client $j \\in \\mathcal{C}$ incurs an assignment cost, which is the distance between $j$ and center in $S$ that it has been assigned to. In this work, we study the \\emph{minimum-norm $k$-clustering problem}, where we are given an arbitrary monotone symmetric norm $f$, and wish to open $k$ centers so as to minimize $f$(assignment-cost vector). This is a powerful generalization, encompassing many classical $k$-clustering problems including the $k$-median, $k$-means, and $k$-center problems. A simple and efficient algorithmic idea is that of \\emph{adaptive sampling}, wherein we randomly choose the location of the next center to open with probability proportional to its ``cost\" under the currently chosen set. While this has yielded fast algorithms for some $k$-clustering problem, little is known for settings \\emph{without} ``min-sum\" objectives. We devise the first adaptive-sampling-based bicriteria constant-factor approximation algorithm for general minimum-norm $k$-clustering, vastly expanding the scope of problems handled by adaptive sampling. For the special case of $\\text{Top}_\\ell$ norms, which form a building block of monotone symmetric norms, we show that adaptive sampling yields an $O(\\log k)$-approximation algorithm.","short_abstract":"In $k$-clustering problems, we are given a metric space $(\\mathcal{C}, d)$, and must choose a set $S$ of $k$ centers to open. Each client $j \\in \\mathcal{C}$ incurs an assignment cost, which is the distance between $j$ and center in $S$ that it has been assigned to. In this work, we study the \\emph{minimum-norm $k$-clu...","url_abs":"https://arxiv.org/abs/2607.12421","url_pdf":"https://arxiv.org/pdf/2607.12421v1","authors":"[\"Haripriya Pulyassary\",\"Chaitanya Swamy\"]","published":"2026-07-14T06:47:16Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}