An incremental algorithm for the uncapacitated facility location problem
Citations Over TimeTop 16% of 2015 papers
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. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 306–311 2015
Related Papers
- Facility Location: Concepts, Models, Algorithms and Case Studies(2009)
- → Multifacility Location Problem(2009)13 cited
- → M UFLP: Universal facility location problem in the p-th power of metric space(2020)8 cited
- Implementing Genetic Algorithm to solve Facility Location Problem(2015)
- → A $$(5.83+\epsilon )$$ ( 5.83 + ϵ ) -Approximation Algorithm for Universal Facility Location Problem with Linear Penalties(2015)