An improved approximation algorithm for k-Median
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917083434975232 |
|---|---|
| author | Young, Neal E. |
| author_facet | Young, Neal E. |
| contents | We give a polynomial-time approximation algorithm for the (not necessarily metric) $k$-Median problem. The algorithm is an $α$-size-approximation algorithm for $α< 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12230 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An improved approximation algorithm for k-Median Young, Neal E. Data Structures and Algorithms 68W25 (Primary) 90-08, 90B80, 90C10, 90C05 (Secondary) F.2.1; G.1.6; G.2.2; G.3 We give a polynomial-time approximation algorithm for the (not necessarily metric) $k$-Median problem. The algorithm is an $α$-size-approximation algorithm for $α< 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. |
| title | An improved approximation algorithm for k-Median |
| topic | Data Structures and Algorithms 68W25 (Primary) 90-08, 90B80, 90C10, 90C05 (Secondary) F.2.1; G.1.6; G.2.2; G.3 |
| url | https://arxiv.org/abs/2511.12230 |