An incremental algorithm for the uncapacitated facility location problem. Issue 4 (6th February 2015)

• Record Type: Journal Article
• Authors: Arulselvan, Ashwin; Maurer, Olaf; Skutella, Martin
• Is Part Of: Networks. Volume 65:Issue 4(2015:Jul.)
• Page Start: 306
• Page End: 311
• Publication Date: 2015-02-06
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21595
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>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 <italic>k</italic>, if the cost of serving the first <italic>ℓ</italic> customers in the sequence is at most <italic>k</italic> times the optimal solution for serving any <italic>ℓ</italic> customers for all possible values of <italic>ℓ</italic>. 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</p> </abstract>