摘要
Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The κ-Facility Location problem further requires that the number of opened facilities is at most κ, where κ is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant ε 〉 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 ＋ √ω ＋ ε, which significantly improves the previous best known ratio （ω ＋ 1）/α for some 1 ≤ α ≤2, and a polynomial-time approximation algorithm for the ω-constrained κ- Facility Location problem with approximation ratio ω ＋ 1 ＋ ε. On the aspect of approximation hardness, we prove that unless NP C DTIME（n^O（log log n））, the ω-constrained Facility Location problem cannot be approximated within 1 ＋ln √ω 1, which slightly improves the previous best known hardness result 1.243 ＋ 0.316 ln（ω - 1）. The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.
Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The κ-Facility Location problem further requires that the number of opened facilities is at most κ, where κ is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant ε 〉 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 ＋ √ω ＋ ε, which significantly improves the previous best known ratio （ω ＋ 1）/α for some 1 ≤ α ≤2, and a polynomial-time approximation algorithm for the ω-constrained κ- Facility Location problem with approximation ratio ω ＋ 1 ＋ ε. On the aspect of approximation hardness, we prove that unless NP C DTIME（n^O（log log n））, the ω-constrained Facility Location problem cannot be approximated within 1 ＋ln √ω 1, which slightly improves the previous best known hardness result 1.243 ＋ 0.316 ln（ω - 1）. The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.
基金
Supported by the National Natural Science Foundation of China for Distinguished Young Scholars under Grant No. 60325206
the National Natural Science Foundation of China for Major International (Regional) Joint Research Project under Grant No. 60310213
the National Natural Science Foundation of China under Grant No. 60573024.
