×

An approximation algorithm for a facility location problem with stochastic demands and inventories. (English) Zbl 1113.90090

Summary: We propose a 2-approximation algorithm for a facility location problem with stochastic demands. At open facilities, inventory is kept such that arriving requests find a zero inventory with (at most) some pre-specified probability. Costs incurred are expected transportation costs, facility operating costs and inventory costs.

MSC:

90B85 Continuous location
90B05 Inventory, storage, reservoirs
90C15 Stochastic programming
90C59 Approximation methods and heuristics in mathematical programming
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V. Arya, N. Garg, R. Khandekar, V. Pandit, A. Meyerson, K. Munagala, Local search heuristics for \(k\); V. Arya, N. Garg, R. Khandekar, V. Pandit, A. Meyerson, K. Munagala, Local search heuristics for \(k\) · Zbl 1323.90031
[2] Batta, R., A queuing location model with expected service time dependent queuing disciplines, Eur. J. Oper. Res., 39, 192-205 (1989) · Zbl 0674.90031
[3] Berman, O.; Sapna, K., Optimal control of service for facilities holding inventory, Comput. Oper. Res., 28, 429-441 (2001) · Zbl 1080.90501
[4] Chudak, F. A.; Shmoys, D. B., Improved approximation algorithms for the uncapacitated facility location problem, SIAM J. Comput., 33, 1-25 (2003) · Zbl 1044.90056
[5] Cornuejols, G.; Nemhauser, G. L.; Wolsey, L. A., The uncapacitated facility location problem, (Mirchandani, P.; Francis, R., Discrete Location Theory (1990), Wiley: Wiley New York), 119-171 · Zbl 0727.90043
[6] Guha, S.; Khuller, S., Greedy strikes backimproved facility location algorithms, J. Algorithms, 31, 228-248 (1999) · Zbl 0928.68137
[7] Guha, S.; Meyerson, A.; Munagala, K., A constant factor approximation algorithm for the fault-tolerant facility location problem, J. Algorithms, 48, 429-440 (2003) · Zbl 1091.90034
[8] Hajiaghayi, M. G.; Mahdian, M.; Mirrokni, V. S., The facility location problem with general cost functions, Networks, 42, 42-47 (2003) · Zbl 1032.90015
[9] Jain, K.; Mahdian, M.; Markakis, E.; Saberi, A.; Vazirani, V., Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM, 50, 795-824 (2003) · Zbl 1325.90060
[10] Jain, K.; Vazirani, V., Approximation algorithms for metric facility location and \(k\)-median problems using the primal-dual schema and Lagrangian relaxation, J. ACM, 48, 274-296 (2001) · Zbl 1138.90417
[11] Korupolu, M. R.; Plaxton, C. G.; Rajaraman, R., Analysis of a local search heuristic for facility location problems, J. Algorithms, 37, 146-188 (2000) · Zbl 0962.68044
[12] M. Mahdian, Facility location and the analysis of algorithms through factor-revealing programs, Ph.D. Thesis, MIT, 2004, available at http://www.math.mit.edu/\( \sim;\); M. Mahdian, Facility location and the analysis of algorithms through factor-revealing programs, Ph.D. Thesis, MIT, 2004, available at http://www.math.mit.edu/\( \sim;\)
[13] M. Mahdian, M. Pal, Universal facility location, in: Proceedings of the 11th Annual European Symposium ESA, Springer, Berlin, Lecture Notes in Computer Science, vol. 2832, 2003, pp. 409-421.; M. Mahdian, M. Pal, Universal facility location, in: Proceedings of the 11th Annual European Symposium ESA, Springer, Berlin, Lecture Notes in Computer Science, vol. 2832, 2003, pp. 409-421. · Zbl 1266.90119
[14] M. Mahdian, Y. Ye, J. Zhang, A 1.52 approximation algorithm for the uncapacitated facility location problem, in: Proceedings of the Fifth International Workshop on Approximation Algorithms for Combinatorial Optimization, Springer, Berlin, Lecture Notes in Computer Science, vol. 2462, 2002, pp. 229-242.; M. Mahdian, Y. Ye, J. Zhang, A 1.52 approximation algorithm for the uncapacitated facility location problem, in: Proceedings of the Fifth International Workshop on Approximation Algorithms for Combinatorial Optimization, Springer, Berlin, Lecture Notes in Computer Science, vol. 2462, 2002, pp. 229-242. · Zbl 1013.90115
[15] M. Mahdian, Y. Ye, J. Zhang, A 2-approximation algorithm for the soft-capacitated facility location problem, Proceedings of the Sixth International Workshop on Approximation Algorithms for Combinatorial Optimization, Springer, Berlin, Lecture Notes in Computer Science, vol. 2764, 2003, pp. 129-140.; M. Mahdian, Y. Ye, J. Zhang, A 2-approximation algorithm for the soft-capacitated facility location problem, Proceedings of the Sixth International Workshop on Approximation Algorithms for Combinatorial Optimization, Springer, Berlin, Lecture Notes in Computer Science, vol. 2764, 2003, pp. 129-140. · Zbl 1279.68358
[16] Marianov, V.; Serra, D., Location-allocation of multiple-server service centers with constrained queues or waiting times, Ann. Oper. Res., 111, 35-50 (2002) · Zbl 1013.90024
[17] R. Ravi, A. Sinha, Hedging uncertainty: approximation algorithms for stochastic optimization problems, in: Proceedings of the 10th International Conference on Integer Programming and Combinatorial Optimization, Springer, Berlin, Lecture Notes in Computer Science, vol. 3064, 2004, pp. 101-115.; R. Ravi, A. Sinha, Hedging uncertainty: approximation algorithms for stochastic optimization problems, in: Proceedings of the 10th International Conference on Integer Programming and Combinatorial Optimization, Springer, Berlin, Lecture Notes in Computer Science, vol. 3064, 2004, pp. 101-115. · Zbl 1092.90531
[18] D. Shmoys, E. Tardos, K. Aardal, Approximation algorithms for facility location problems, in: Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 265-274.; D. Shmoys, E. Tardos, K. Aardal, Approximation algorithms for facility location problems, in: Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 265-274. · Zbl 0962.68008
[19] D. Shmoys, C. Swamy, Stochastic optimization is (almost) as easy as deterministic optimization, in: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 228-237.; D. Shmoys, C. Swamy, Stochastic optimization is (almost) as easy as deterministic optimization, in: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 228-237.
[20] M. Sviridenko, Personal communication, Cited in S. Guha, Approximation algorithms for facility location problems, Ph.D. Thesis, Stanford, 2000, downloadable from http://Theory.Stanford.EDU/\( \sim;\); M. Sviridenko, Personal communication, Cited in S. Guha, Approximation algorithms for facility location problems, Ph.D. Thesis, Stanford, 2000, downloadable from http://Theory.Stanford.EDU/\( \sim;\)
[21] Wang, Q.; Batta, R.; Rump, C., Algorithms for a facility location problem with stochastic customer demand and immobile servers, Ann. Oper. Res., 111, 17-34 (2002) · Zbl 1013.90023
[22] Wolf, R. W., Stochastic Modeling and the Theory of Queues (1989), Prentice-Hall International Series in Industrial and System Engineering · Zbl 0701.60083
[23] J. Zhang, B. Chen, Y. Ye, A multi-exchange local search algorithm for the capacitated facility location problem, in: Proceedings of the 10th International Conference on Integer Programming and Combinatorial Optimization, Springer, Berlin, Lecture Notes in Computer Science, vol. 3064, 2004, pp. 219-233.; J. Zhang, B. Chen, Y. Ye, A multi-exchange local search algorithm for the capacitated facility location problem, in: Proceedings of the 10th International Conference on Integer Programming and Combinatorial Optimization, Springer, Berlin, Lecture Notes in Computer Science, vol. 3064, 2004, pp. 219-233. · Zbl 1092.90525
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.