Premium
An incremental algorithm for the uncapacitated facility location problem
Author(s) -
Arulselvan Ashwin,
Maurer Olaf,
Skutella Martin
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21595
Subject(s) - sequence (biology) , benchmark (surveying) , facility location problem , competitive analysis , computer science , set (abstract data type) , mathematical optimization , algorithm , upper and lower bounds , mathematics , mathematical analysis , genetics , geodesy , biology , programming language , geography
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. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 306–311 2015