{"id":"openai-math/The-Approximation-Threshold-for-Metric-k-Median","pdf":"https://github.com/openai/math/blob/main/preprints/The-Approximation-Threshold-for-Metric-k-Median-September-24-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/The-Approximation-Threshold-for-Metric-k-Median-September-24-2026","tags":["approximation-algorithms","k-median","combinatorial-optimization"],"score":0,"title":"The approximation threshold for metric k-median","domain":"Theoretical computer science","family":"125","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"For every fixed ε > 0, we give a deterministic polynomial-time $`(1+2/e+\\varepsilon)`$-approximation for finite rational metric k -median with specified candidate facilities, opening at most k facilities. Under $`P\\ne NP`$, the infimum approximation factor in this model is therefore $`1+2/e`$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":false,"family_title":"The metric k -median approximation threshold and recovery"}