k-median approximation breaks factor 2: new 1.95-LMP algorithm on arXiv after OpenAI's solve
thomasahle · x · 2026-10-16
The team behind AlgoSvensson announced their better-than-2 approximation for k-median is now on arXiv (2610.18144), days after OpenAI solved the same historic problem their students had worked on for over a year.
- The classic Greedy algorithm's 2-LMP guarantee dominated k-median for two decades; it was only recently nudged by local-search post-processing (η≈2.25×10⁻⁷).
- This work changes the algorithm itself: generalizing the classical linear bid into a richer family of bidding functions, proving a polynomial-time 1.95-LMP approximation — a large improvement over the long-standing factor of 2.
- The generalized bids can be made smooth (log-adaptive), yielding a 1.95-approximation opening k+Oε(log n) centers; combined with a (1.89+ε)-approximation for stable instances in a companion paper.
- Special credit to Toni Jubés Monforte, whose Master's thesis two years ago seeded the factor-revealing LP analysis.
More from Research
- New findings suggest LLMs naturally develop concept-specialized neurons — burny_tech · 2026-10-16
- Quanquan Gu questions whether math rigor became optional in interpretability — burny_tech · 2026-10-16
- Fine-tuning Qwen 7B only on "safe" nuclear war games still taught it to nuke — KnowledgeOk7634 · 2026-10-16
- Berkeley paper uses the Midas myth to rethink robotics beyond human imitation — begusgasper · 2026-10-16
- 31 Tech Curves Visualized: Kurzweil's $1,000-Brain-Compute Call Missed by 400x — cpaik · 2026-10-16
- DeepMind Paper: First-Price Auctions in Agentic Markets Reach 1-1/e^2 Efficiency — dair_ai · 2026-10-16