Primal–dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach

The main contribution of this work is to propose a primal–dual combinatorial 3(1+ε)3(1+ε)-approximation algorithm for the two-level facility location problem (2-LFLP) by exploring the approximation oracle concept. This result improves the previous primal–dual 6-approximation algorithm for the multilevel facility location problem, and also matches the previous primal–dual approximation ratio for the single-level facility location problem. One of the major merits of primal–dual type algorithms is their easy adaption to other variants of the facility location problems. As a demonstration, our primal–dual approximation algorithm can be easily adapted to several variants of the 2-LFLP, including models with stochastic scenario, dynamically arrived demands, and linear facility cost.