Nikhil Bansal, Alberto Caprara, et al.
SIAM Journal on Computing
In this paper, 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 NP is contained in DTIME(nO(log log n)) for the case when k = 2. For the case of general k (tendining 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 [22], 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 [17], which holds even for the case of k = 1. Copyright © SIAM.
Nikhil Bansal, Alberto Caprara, et al.
SIAM Journal on Computing
Nikhil Bansal, Maxim Sviridenko
STOC 2006
Maurice Queyranne, Maxim Sviridenko
Journal of Algorithms
Ph. Baptiste, J. Carlier, et al.
Discrete Applied Mathematics