We consider the k-level facility location problem with soft capacities （k-LFLPSC）. In the k- LFLPSC, each facility i has a soft capacity ui along with an initial opening cost fi ≥O, i.e., the capacity of facility i...We consider the k-level facility location problem with soft capacities （k-LFLPSC）. In the k- LFLPSC, each facility i has a soft capacity ui along with an initial opening cost fi ≥O, i.e., the capacity of facility i is an integer multiple of ui incurring a cost equals to the corresponding multiple of fi. We firstly propose a new bifactor （ln（1/β）/（1 -β）, 1 ＋ 2/（1 - β））-approximation algorithm for the k-level facility location problem （k-LFLP）, where β∈（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.展开更多
基金supported in part by Natural Science Foundation of China under Grant No.11501412supported by Natural Science Foundation of China under Grant No.11531014
文摘We consider the k-level facility location problem with soft capacities （k-LFLPSC）. In the k- LFLPSC, each facility i has a soft capacity ui along with an initial opening cost fi ≥O, i.e., the capacity of facility i is an integer multiple of ui incurring a cost equals to the corresponding multiple of fi. We firstly propose a new bifactor （ln（1/β）/（1 -β）, 1 ＋ 2/（1 - β））-approximation algorithm for the k-level facility location problem （k-LFLP）, where β∈（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.
