An Improved Approximation Algorithm for the k-Level Facility Location Problem with Soft Capacities

作者：Wu, Chen-chen; Xu, Da-chuan^*

来源：Acta Mathematicae Applicatae Sinica-English Series, 2017, 33(4): 1015-1024.

DOI：10.1007/s10255-017-0714-x

• facility location
• approximation algorithm
• soft capacity

We consider the k-level facility location problem with soft capacities (k-LFLPSC). In the k-LFLPSC, each facility i has a soft capacity u(i) along with an initial opening cost f(i) >= 0, i.e., the capacity of facility i is an integer multiple of u(i) incurring a cost equals to the corresponding multiple of f(i) . We firstly propose a new bifactor (ln(1/beta)/(1 - beta),1+2/(1 - beta))-approximation algorithm for the k-level facility location problem (k-LFLP), where beta is an element of (0, 1) is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation.

• 出版日期2017-10
• 单位北京工业大学