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

3 Citations (Scopus)
57 Downloads (Pure)

Abstract

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
Volume46
Issue number2
Early online date31 Jan 2018
DOIs
Publication statusPublished - 1 Mar 2018

Keywords

  • Local search
  • Perturbation resilience
  • Facility location problem

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

  • Cite this