An incremental algorithm for uncapacitated facility location problem

Ashwin Arulselvan, Olaf Maurer, Martin Skutella

Research output: Contribution to journalArticle

3 Citations (Scopus)
26 Downloads (Pure)

Abstract

We study the incremental facility location problem, wherein we are given an instance of the uncapacitated facility location problem (UFLP) and seek an incremental sequence of opening facilities and an incremental sequence of serving customers along with their fixed assignments to facilities open in the partial sequence. We say that a sequence has a competitive ratio of k, if the cost of serving the first ℓ customers in the sequence is at most k times the optimal solution for serving any ℓ customers for all possible values of ℓ. We provide an incremental framework that computes a sequence with a competitive ratio of at most eight and a worst-case instance that provides a lower bound of three for any incremental sequence. We also present the results of our computational experiments carried out on a set of benchmark instances for the UFLP. The problem has applications in multistage network planning.
Original languageEnglish
Pages (from-to)306–311
Number of pages6
JournalNetworks
Volume65
Issue number4
Early online date6 Feb 2015
DOIs
Publication statusPublished - 1 Jul 2015

    Fingerprint

Keywords

  • incremental algorithm
  • facility location problem
  • network design
  • competitive ratio
  • robust location

Cite this