{"ID":2841342,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.12230","arxiv_id":"2511.12230","title":"An improved approximation algorithm for k-Median","abstract":"We give a polynomial-time approximation algorithm for the (not necessarily metric) $k$-Median problem. The algorithm is an $α$-size-approximation algorithm for $α\u003c 1 + 2 \\ln(n/k)$. That is, it guarantees a solution having size at most $α\\times k$, and cost at most the cost of any size-$k$ solution. This is the first polynomial-time approximation algorithm to match the well-known bounds of $H_Δ$ and $1 + \\ln(n/k)$ for unweighted Set Cover (a special case) within a constant factor. It matches these bounds within a factor of 2. The algorithm runs in time $O(k m \\log(n/k) \\log m)$, where $n$ is the number of customers and $m$ is the instance size.","short_abstract":"We give a polynomial-time approximation algorithm for the (not necessarily metric) $k$-Median problem. The algorithm is an $α$-size-approximation algorithm for $α\u003c 1 + 2 \\ln(n/k)$. That is, it guarantees a solution having size at most $α\\times k$, and cost at most the cost of any size-$k$ solution. This is the first po...","url_abs":"https://arxiv.org/abs/2511.12230","url_pdf":"https://arxiv.org/pdf/2511.12230v1","authors":"[\"Neal E. Young\"]","published":"2025-11-15T14:15:20Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}