# Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median

arXiv: https://arxiv.org/abs/2207.05150 · HTML: https://mlsanity.com/paper/2207.05150/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2022.

## Built on by (most cited first, 2 of 2)

- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Hierarchical F-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs](https://mlsanity.com/paper/2607.13217/) (2026)

## Abstract (arXiv)

The Uncapacitated Facility Location (UFL) problem is one of the most fundamental clustering problems: Given a set of clients C and a set of facilities F in a metric space (C cup F, dist) with facility costs open : F → ℝ^+, the goal is to find a set of facilities S subseteq F to minimize the sum of the opening cost open(S) and the connection cost d(S) := sump ∈ C minc ∈ S dist(p, c). An algorithm for UFL is called a Lagrangian Multiplier Preserving (LMP) α approximation if it outputs a solution Ssubseteq F satisfying open(S) + d(S) ≤ open(S^*) + α d(S^*) for any S^* subseteq F. The best-known LMP approximation ratio for UFL is at most 2 by the JMS algorithm of Jain, Mahdian, and Saberi based on the Dual-Fitting technique. We present a (slightly) improved LMP approximation algorithm for UFL. This is achieved by combining the Dual-Fitting technique with Local Search, another popular technique to address clustering problems. From a conceptual viewpoint, our result gives a theoretical evidence that local search can be enhanced so as to avoid bad local optima by choosing the initial feasible solution with LP-based techniques. Using the framework of bipoint solutions, our result directly implies a (slightly) improved approximation for the k-Median problem from 2.6742 to 2.67059.