k-median breaks the factor-2 barrier

Your AI and this story

Key facts

• Paper: arXiv 2610.18144 [cs.DS], 13 Oct 2026; authors at EPFL, Google Research, Carnegie Mellon and NYU (incl. Ola Svensson, Vincent Cohen-Addad, Anupam Gupta)
• Main result: a polynomial-time 1.95-LMP (Lagrangian-multiplier-preserving) approximation for facility location using the bid β(α, d) = [α − 1.224 d]+; the previous best LMP factor was 2 − η with η ≈ 2.25 × 10⁻⁷ (Cohen-Addad, Grandoni, Lee, Schwiegelshohn)
• k-median: a 1.95-approximation opening k + O(log n) centers; with a (1.89 + ε)-approximation for stable instances in the companion Part II, this gives a better-than-2 polynomial-time approximation. Prior state: (2 + ε) (Cohen-Addad et al. 2025; Byrka et al. 2026); k-median is hard to approximate below 1 + 2/e
• GPT-6 Astra (Remark 1.5): ‘GPT-6 Astra managed to improve the LMP approximation ratio to 1.844’, with a 13-term bidding function, and ‘managed to prove that for any admissible bidding function … the supremum of the factor revealing program … has value at least 1.8’, so the approach cannot go below 1.8
• AI statement: ‘The mathematical proofs presented in this work (apart from Remark 1.5) were developed solely by the authors without the use of AI.’ GPT-5.6 Sol and GPT-6 Astra were used for proof-checking and writing help; ‘The lean certificates mentioned in Remark 1.5 and the certificate for Theorem 4.4 were obtained by GPT-6 Astra’
• Lean certificates: github.com/epfl-thl2/project-k-median (reachable on 14 Oct 2026)
• Concurrent work, as described in the paper: OpenAI announced on 6 Oct two better-than-2 k-median algorithms, an optimal (1 + 2/e + ε)-approximation extending Byrka et al.’s iterative rounding and a (2 − σ)-approximation; a group around Byrka and Shi Li independently reached 2 − σ. These OpenAI claims were not checked here