An incremental algorithm for the uncapacitated facility location problem

被引:8
作者
Arulselvan, Ashwin [1 ,3 ]
Maurer, Olaf [2 ]
Skutella, Martin [2 ]
机构
[1] Univ Strathclyde, Dept Management Sci, Glasgow, Lanark, Scotland
[2] Tech Univ Berlin, Inst Math, Berlin, Germany
[3] Tech Univ Berlin, Berlin, Germany
关键词
incremental algorithm; facility location problem; network design; competitive ratio; robust location; APPROXIMATION ALGORITHM;
D O I
10.1002/net.21595
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 306-311 2015
引用
收藏
页码:306 / 311
页数:6
相关论文
共 50 条
[41]   AN APPROXIMATION ALGORITHM FOR THE k-LEVEL FACILITY LOCATION PROBLEM WITH SUBMODULAR PENALTIES [J].
Li, Gaidi ;
Wang, Zhen ;
Xu, Dachuan .
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2012, 8 (03) :521-529
[42]   A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties [J].
Du, Donglei ;
Lu, Ruixing ;
Xu, Dachuan .
ALGORITHMICA, 2012, 63 (1-2) :191-200
[43]   A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties [J].
Li, Yu ;
Du, Donglei ;
Xiu, Naihua ;
Xu, Dachuan .
THEORETICAL COMPUTER SCIENCE, 2013, 476 :109-117
[44]   An approximation algorithm for the nth power metric facility location problem with linear penalties [J].
Yishui Wang ;
Dachuan Xu ;
Donglei Du ;
Chenchen Wu .
Optimization Letters, 2017, 11 :983-993
[45]   A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties [J].
Donglei Du ;
Ruixing Lu ;
Dachuan Xu .
Algorithmica, 2012, 63 :191-200
[46]   An Approximation Algorithm for the Two-Stage Distributionally Robust Facility Location Problem [J].
Wu, Chenchen ;
Du, Donglei ;
Xu, Dachuan .
ADVANCES IN GLOBAL OPTIMIZATION, 2015, 95 :99-107
[47]   Approximation algorithms for the stochastic priority facility location problem [J].
Li, Gaidi ;
Wang, Zhen ;
Wu, Chenchen .
OPTIMIZATION, 2013, 62 (07) :919-928
[48]   The probabilistic uncapacitated open vehicle routing location problem [J].
Averbakh, Igor ;
Yu, Wei .
NETWORKS, 2023, 82 (01) :68-83
[49]   An Approximation Algorithm for the Dynamic Facility Location Problem with Submodular Penalties [J].
Chun-yan JIANG ;
Gai-di LI ;
Zhen WANG .
Acta Mathematicae Applicatae Sinica, 2014, (01) :187-192
[50]   An approximation algorithm for a competitive facility location problem with network effects [J].
Kung, Ling-Chieh ;
Liao, Wei-Hung .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2018, 267 (01) :176-186