An Approximation Framework for Bounded Facility Location Problems

摘要

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.