Approximation algorithm for uniform bounded facility location problem |
| |
Authors: | Weng Kerui |
| |
Affiliation: | 1. School of Economy and Management, China University of Geosciences, Wuhan, 430070, P.R. China
|
| |
Abstract: | 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+? 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|