Perturbation resilience for the facility location problem

Bodo Manthey (Corresponding Author), Matthijs B. Tijink

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
20 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

Fingerprint

Facility Location Problem
Resilience
Perturbation
Local Search
Optimal Solution
Costs
Heuristics
Facility location
Location problem
Local search
Optimal solution

Keywords

  • Local search
  • Perturbation resilience
  • Facility location problem

Cite this

Manthey, Bodo ; Tijink, Matthijs B. / Perturbation resilience for the facility location problem. In: Operations research letters. 2018 ; Vol. 46, No. 2. pp. 215-218.
@article{1560da36a4224fd39a3938772e41a278,
title = "Perturbation resilience for the facility location problem",
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.",
keywords = "Local search, Perturbation resilience, Facility location problem",
author = "Bodo Manthey and Tijink, {Matthijs B.}",
year = "2018",
month = "3",
day = "1",
doi = "10.1016/j.orl.2018.01.003",
language = "English",
volume = "46",
pages = "215--218",
journal = "Operations research letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "2",

}

Perturbation resilience for the facility location problem. / Manthey, Bodo (Corresponding Author); Tijink, Matthijs B.

In: Operations research letters, Vol. 46, No. 2, 01.03.2018, p. 215-218.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Perturbation resilience for the facility location problem

AU - Manthey, Bodo

AU - Tijink, Matthijs B.

PY - 2018/3/1

Y1 - 2018/3/1

N2 - 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.

AB - 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.

KW - Local search

KW - Perturbation resilience

KW - Facility location problem

UR - http://www.scopus.com/inward/record.url?scp=85041416508&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2018.01.003

DO - 10.1016/j.orl.2018.01.003

M3 - Article

VL - 46

SP - 215

EP - 218

JO - Operations research letters

JF - Operations research letters

SN - 0167-6377

IS - 2

ER -