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 -