Inapproximability of the Multilevel Uncapacitated Facility Location Problem
Ravishankar Krishnaswamy, Maxim I. Sviridenko · ACM Transactions on Algorithms · 2016
In this article, we present improved inapproximability results for the k -level uncapacitated facility location problem. In particular, we show that there is no polynomial time approximation algorithm with performance guarantee better than 1.539 unless P = NP for the case when k = 2. For the case of general k (tending to infinity), we obtain a better hardness factor of 1.61. Interestingly, our results show that the two-level problem is computationally harder than the well-known uncapacitated facility location problem ( k = 1) since the best-known approximation guarantee for the latter problem is 1.488 due to Li [2013], and our inapproximability is a factor of 1.539 for the two-level problem. The only inapproximability result known before for this class of metric facility location problems is the bound of 1.463 due to Guha and Khuller [1999], which holds even for the case of k = 1.