{"id":"openai-math/Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median","pdf":"https://github.com/openai/math/blob/main/preprints/Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median-September-24-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Single-Exponential-Recovery-and-Bounded-Price-Strictness-for-Metric-k-Median-September-24-2026","tags":["combinatorial-optimization","k-median","approximation-algorithms"],"score":0,"title":"Single-exponential recovery and bounded-price strictness for metric k-median","domain":"Theoretical computer science","family":"125","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We give an exact-budget recovery algorithm for metric k -median with single-exponential dependence on the number of comparison clusters without accurate, distinct proxies in a supplied anchor solution. On positive integral metrics of polynomially bounded diameter, a sufficiently small total proxy error and logarithmically many such clusters yield a $`(1+2/e+\\varepsilon)`$ approximation in polynomial time with arbitrarily high success probability. We also prove bounded-price strictness for one compatible execution of the logarithmic-surplus construction. Together the recovery and payment…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":true,"family_title":"The metric k -median approximation threshold and recovery"}