A General k-Level Uncapacitated Facility Location Problem

作者：Li Rongheng^*; Huang Huei Chuen

来源：4th International Conference on Intelligent Computing, 2008-09-15 to 2008-09-18.

• Approximation algorithm
• Facility location
• Complexity
• k-level

In this paper a general k-level uncapacitated facility location problem(k-GLUFLP) is proposed. It is shown that the 2-level uncapacitated facility location problem with no fixed cost(2-GLUFLNP) is strong NP-complete and a heuristic algorithm with worst case ratio of 3/2 is given for 2-GLUFLNP when the service costs are assumed to be in the metric space. We also present a randomized 3-approximation algorithm for the k-GLUFLP, when k is a fixed integer.

• 出版日期2008
• 单位湖南师范大学