Perturbation resilience for the facility location problem

We prove that local search for FLP succeeds in finding the optimal solution for γ-perturbation resilient instances for γ≥3, and we show that this is tight.