Perturbation resilience for the facility location problem

Bodo Manthey* (Corresponding Author), Matthijs B. Tijink

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
151 Downloads (Pure)


We analyze a simple local search heuristic for the facility location problem using the notion of perturbation resilience: an instance is γ-perturbation resilient if all costs can be perturbed by a factor of γ without changing the optimal solution. 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.

Original languageEnglish
Pages (from-to)215-218
Number of pages4
JournalOperations research letters
Issue number2
Early online date31 Jan 2018
Publication statusPublished - 1 Mar 2018


  • Local search
  • Perturbation resilience
  • Facility location problem


Dive into the research topics of 'Perturbation resilience for the facility location problem'. Together they form a unique fingerprint.

Cite this