TY - GEN
T1 - An approximation framework for bounded facility location problems
AU - Luo, Wenchang
AU - Su, Bing
AU - Xu, Yao
AU - Lin, Guohui
N1 - Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.
PY - 2018
Y1 - 2018
N2 - We study the bounded metric uncapacitated facility location (bUFL) problem and its two variants, the bounded fault-tolerant facility location (bFTFL) problem and the bounded fault-tolerant facility placement (bFTFP) problem. We propose a unified approximation framework built on the state-of-the-art approximation algorithms for the three unbounded counterparts, leading to a (2.488 + ε) -approximation algorithm for the bUFL problem in the Euclidean plane, a (1.488+H(n)) -approximation algorithm for the bUFL problem, a (1.725+H(n)) -approximation algorithm for the bFTFL problem, and a (1.515+H(n)) -approximation algorithm for the bFTFP problem in a general metric space. We also prove an inapproximability result for all the three bounded facility location problems in a general metric space.
AB - We study the bounded metric uncapacitated facility location (bUFL) problem and its two variants, the bounded fault-tolerant facility location (bFTFL) problem and the bounded fault-tolerant facility placement (bFTFP) problem. We propose a unified approximation framework built on the state-of-the-art approximation algorithms for the three unbounded counterparts, leading to a (2.488 + ε) -approximation algorithm for the bUFL problem in the Euclidean plane, a (1.488+H(n)) -approximation algorithm for the bUFL problem, a (1.725+H(n)) -approximation algorithm for the bFTFL problem, and a (1.515+H(n)) -approximation algorithm for the bFTFP problem in a general metric space. We also prove an inapproximability result for all the three bounded facility location problems in a general metric space.
KW - Approximation algorithm
KW - Bounded uncapacitated facility location
KW - Weighted dominating set in unit disk graphs
KW - Weighted set multi-cover
UR - http://www.scopus.com/inward/record.url?scp=85049693921&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-94776-1_30
DO - 10.1007/978-3-319-94776-1_30
M3 - Conference article
AN - SCOPUS:85049693921
SN - 9783319947754
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 353
EP - 364
BT - Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
A2 - Zhu, Daming
A2 - Wang, Lusheng
PB - Springer Verlag
T2 - 24th International Conference on Computing and Combinatorics Conference, COCOON 2018
Y2 - 2 July 2018 through 4 July 2018
ER -