---
id: "2026-10-13-k-median-better-than-2-approximation-epfl"
url: "https://postcutoff.com/e/2026-10-13-k-median-better-than-2-approximation-epfl/"
as_of: "2026-10-15T10:09:00+02:00"
date: "2026-10-13"
date_precision: day
category: science
importance: 3
confidence: high
status: [Event confirmed, Awaiting review]
verification: Lean-verified
sources: 2
editor: human editor
human_review: null
version: "2026-10-14"
---

As of: 2026-10-15 10:09 CEST.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/
Canonical page: https://postcutoff.com/e/2026-10-13-k-median-better-than-2-approximation-epfl/

# k-median breaks the factor-2 barrier

Full title: k-median breaks the factor-2 barrier: EPFL-led team gives a 1.95-LMP algorithm; GPT-6 Astra pushes it to 1.844 and proves a 1.8 limit, both with Lean certificates

arXiv 2610.18144 (13 Oct 2026), "A Better-than-2 Approximation for k-Median Part I: The Power of General Bids", by Buhai, Cohen-Addad, Fleischmann, Gupta, Jubés Monforte, Pittu, Stouras, Svensson and Vogl, replaces the linear bid in the Jain–Mahdian–Markakis–Saberi–Vazirani greedy algorithm with general bidding functions. That gives a 1.95-LMP algorithm for facility location, where the factor 2 had essentially stood for two decades, and, with a companion paper, a better-than-2 approximation for k-median. The authors say their proofs were human, but GPT-6 Astra found a bidding function reaching 1.844 and proved that the method cannot go below 1.8, both with Lean certificates.

## 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

## What happened

The greedy algorithm of Jain, Mahdian, Markakis, Saberi and Vazirani (2002–03) has been the engine behind the best k-median guarantees through its 2-LMP guarantee for facility location. A 2023 local-search analysis improved it by only about 2.25 × 10⁻⁷. In [arXiv 2610.18144](https://arxiv.org/abs/2610.18144) (13 Oct 2026), a team from EPFL, Google Research, CMU and NYU changes the algorithm itself: clients bid with general functions of their budget and distance instead of the classical linear bid. The bid [α − 1.224 d]+ gives a 1.9499-LMP guarantee, which they make "log-adaptive" to get a polynomial-time 1.95-approximation opening k + O(log n) centers. With a (1.89 + ε) algorithm for stable instances from the companion Part II, this gives a better-than-2 approximation for k-median.

The paper separates human and AI work. The main proofs "were developed solely by the authors without the use of AI". In Remark 1.5, GPT-6 Astra found a 13-term bidding function with LMP ratio 1.844, and proved that no admissible bidding function can push this factor-revealing program below 1.8. Lean certificates for both, and for the paper's Theorem 4.4, "were obtained by GPT-6 Astra" and are on GitHub.

The authors also note concurrent work. OpenAI announced on 6 Oct two better-than-2 k-median algorithms, including an optimal (1 + 2/e + ε)-approximation, and a group around Jarosław Byrka and Shi Li independently reached 2 − σ. Those claims were not checked for this entry.

## Why it matters

Factor 2 was a well-known barrier in clustering approximation. Here it falls to human work in the same weeks as OpenAI's claimed AI-found algorithms. The AI's own contribution is typical of the stronger 2026 collaborations: it tuned the construction further and proved where the method stops, with machine-checkable certificates.

## What is disputed or not yet verified

- Verification: Unrefereed preprint; Lean certificates for the AI-found bounds and for Theorem 4.4

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 166 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 105 days after its cutoff
- Gemini 4 Argon (training cutoff March 2026): 196 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 135 days after its cutoff

## Sources

1. [arXiv 2610.18144: A Better-than-2 Approximation for k-Median Part I: The Power of General Bids](https://arxiv.org/abs/2610.18144) (arxiv.org, paper)
2. [GitHub: epfl-thl2/project-k-median (Lean certificates)](https://github.com/epfl-thl2/project-k-median) (github.com, code)

## Changes

- 2026-10-14 (filed): Created from the arXiv paper

## Related

- 2026-10-14: [Mid-October 2026: arXiv results with disclosed AI help](https://postcutoff.com/e/2026-10-14-ai-assisted-results-mid-october-2026/index.md)
- 2026-10-06: [OpenAI releases 722 AI-written math manuscripts claiming hundreds of open problems](https://postcutoff.com/e/2026-10-06-openai-math-release-722-manuscripts/index.md)