Approximation algorithm for uniform bounded facility location problem

作者：Weng Kerui^*

来源：Journal of Combinatorial Optimization, 2013, 26(2): 284-291.

DOI：10.1007/s10878-012-9461-3

• Facility location
• Routing costs bound
• Approximation algorithm
• Benders decomposition

The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound M. After building a mixed 0-1 integer programming model for UBFLP, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853+I mu for UBFLP on plane, which is composed of the algorithm by Dai and Yu (Theor. Comp. Sci. 410:756-765, 2009) and the schema of Xu and Xu (J. Comb. Optim. 17:424-436, 2008). We also provide a heuristic algorithm based on Benders decomposition to solve UBFLP on general graphes, and the computational experience shows that the heuristic works well.

• 出版日期2013-8
• 单位中国地质大学（北京）