Abstract
We propose a quasi-greedy algorithm for approximating the classical uncapacitated 2-level facility location problem (2-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization 2-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of our algorithm is that it combines the technique of randomized rounding with that of dual fitting.
This new approach enables us to approximate the metric 2-LFLP in polynomial time with a ratio of 1.77, a significant improvement on the previously known approximation ratios. Moreover, our approach results in a local improvement procedure for the 2-LFLP, which is useful in improving the approximation guarantees for several other multi-level facility location problems. An additional result of our approach is an O(ln (n))-approximation algorithm for the non-metric 2-LFLP, where n is the number of clients. This is the first non-trivial approximation for a non-metric multi-level facility location problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aardal, K., Labbe, M., Leung, J., Queyranne, M.: On the two-level uncapacitated facility location problem. INFORMS Journal on Computing 8, 289–301 (1996)
Aardal, K., Chudak, F.A., Shmoys, D.B.: A 3-approximation algorithm for the k-level uncapacitated facility location problem. Information Processing Letters 72, 161–167 (1999)
Ageev, A.: Improved approximation algorithms for multilevel facility location problems. Oper. Res. Letters 30, 327–332 (2002)
Ageev, A., Sviridenko, M.: An 0.828-approximation algorithm for uncapacitated facility location problem. Discrete Applied Mathematics 93, 289–296, (1999)
Ageev, A., Ye, Y., Zhang, J.: Improved Combinatorial Apporixmation Algorithms for the k-Level Facility Location Problem. In: Proceedings of The 30th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 2719, 2003, pp. 145–156
Bumb, A.: An approximation algorithm for the maximization version of the two level uncapacitated facility location problem. Operations Research Letters 29(4), 155–161 (2001)
Bumb, A.F., Kern, W.: A simple dual ascent algorithm for the multilevel facility location problem. In: 4th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2001), LNCS 2129, 2001, pp. 55–62
Barros, A.I., Labbe, M.: A general model for the uncapacitated facility and depot location problem. Location Science 2, 173–191 (1994)
Carr, R.D., Fleischer, L., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 106–115
Chardaire, P.: Facility Location Optimization and Cooperative Games. Ph.d. Thesis, School of Information Systems, University of East-Anglia, Norwich NR4 7TJ, UK, 1998
Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation Algorithms for Directed Steiner Problems. Journal of Algorithms 33, 73–91 (1999)
Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM Journal on Computing 34(4), 803–824 (2005)
Chekuri, C., Even, G., Guy Kortsarz: A combinatorial approximation algorithm for the group Steiner problem. submitted to Discrete Applied Mathematics
Cornuéjols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Mngt Sci. 23, 789–810 (1977)
Cornuéjols, G., Nemhauser, G.L., Wolsey, L.A.: The uncapacitated facility location problem. In: P. Mirchandani and R. Francis, (eds.) Discrete Location Theory, Wiley, New York, 1990, pp. 119–171
Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM Journal on Computing 33, 1–25 (2003)
Edwards, N.: Approximation algorithms for the multi-level facility location problem. Ph.D. Thesis, School of Operations Research and Industrial Engineering, Cornell University, 2001
Erdös, P., Selfridge, J.L.: On a combinatorial game. J. Combinatorial Theory, Ser. A 14, 298–301 (1973)
Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM 45, 634–652 (1998)
Gao, J.J., Robinson, E.P. Jr.: A dual-based optimization procedure for the two-echelon uncapacitated facility location problem. Naval Research Logistics 839, 191–212 (1992)
Gao, J.J., Robinson, E.P. Jr.: Uncapacitated facility location: General solution procedure and computational experience. European Journal of Operational Research 76, 410–427 (1994)
Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. Journal of Algorithms 31, 228–248 (1999)
Hochbaum, D.S.: Heuristics for the fixed cost median problem. Mathematical Programming 22(2), 148–162 (1982)
Kaufman, L., Eede, M.V., Hansen, P.: A plant and warehouse location problem. Operations Research Quarterly 28, 547–554 (1977)
Labbe, M.: The multi-level uncapacitated facility location problem is not submodular. European Journal of Operational Research 72, 607–609 (1996)
Levin, A.: Personal Communication, 2003
Guha, S., Meyerson, A., Munagala, K.: Hierarchical placement and network design problems. In: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), 2000, pp. 603–612
Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), 2002, pp. 731–740
Jain, K., Mahdian, M., Salavatipour, M.R.: Packing Steiner trees. In: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 266–274
Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), Lecture Notes in Computer Science, 2462, 2002, pp. 229–242
Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: 6th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2003), Lecture Notes in Computer Science, 2764, 2003, pp. 129–140
Meyerson, A., Munagala, K., Plotkin, S.: Cost-distance: two-metric network design. In: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), 2000, pp. 624–630
Ro, H., Tcha, D.: A branch-and-bound algorithm for the two-level uncapacitated facility location problem with some side constraints. European Journal of Operational Research 18, 349–358 (1984)
Robinson, E.P. Jr., Gao, L.: A new formulation and linear programming based optimization procedure for the two-echelon uncapacitated facility location problem. Annals of the Society of Logistics Engineers 2, 39–59
Robinson, E.P. Jr., Gao, L., Muggenborg, S.D.: Designing an integrated distribution system at DowBrands Inc. Interfaces 23, 107–117 (1993)
Shmoys, D.B.: Approximation algorithms for facility location problems. In: 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), LNCS 1913, 2000, pp. 27–33
Shmoys, D.B., Tardos, E., Aardal, K.I.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing 29th STOC, 1997, pp. 265–274
Tcha, D., Lee, B.: A branch-and-bound algorithm for the multi-level uncapacitated facility location problem. European Journal of Operational Research 18, 35–43 (1984)
Zhang, J., Ye, Y.: A Note on the Maximization Version of the Multi-level Facility Location Problem. Operations Research Letters 30(5), 333–335 (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of this paper appeared in the Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2004.
Rights and permissions
About this article
Cite this article
Zhang, J. Approximating the two-level facility location problem via a quasi-greedy approach. Math. Program. 108, 159–176 (2006). https://doi.org/10.1007/s10107-006-0704-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0704-x