Perturbation resilience for the facility location problem

Bodo Manthey; Matthijs B. Tijink

doi:10.1016/j.orl.2018.01.003

Perturbation resilience for the facility location problem

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

^*Corresponding author for this work

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

5 Citations (Scopus)

202 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 language	English
Pages (from-to)	215-218
Number of pages	4
Journal	Operations research letters
Volume	46
Issue number	2
Early online date	31 Jan 2018
DOIs	https://doi.org/10.1016/j.orl.2018.01.003
Publication status	Published - 1 Mar 2018

Keywords

Local search
Perturbation resilience
Facility location problem

Access to Document

10.1016/j.orl.2018.01.003

Manthey2018perturbationAccepted author version, 269 KBLicence: CC BY-NC-ND

Cite this

@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 = mar,

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 B.V.",

number = "2",

}

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

AN - SCOPUS:85041416508

SN - 0167-6377

VL - 46

SP - 215

EP - 218

JO - Operations research letters

JF - Operations research letters

IS - 2

ER -

Perturbation resilience for the facility location problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this