Abstract
We consider important generalizations of a wide class of traditional deterministic inventory and facility location models that we call inventory/facility location models with market selection. Instead of the traditional setting, we are given a set of markets, each specified by a sequence of demands and associated with a revenue. Decisions are made in two stages. We first make a decision of what markets to select, where all other markets are rejected. Next we have to construct a minimum-cost production plan (facility layout) to satisfy all of the demands of all the selected markets. The goal is to minimize the overall lost revenues of rejected markets and the production (facility openings and connection) costs. We show how to leverage existing approximation results for the traditional models to corresponding results for the counterpart models with market selection. More specifically, any LP based α–approximation for the traditional model can be leveraged to a \(\frac{1}{_{1-e}-\frac{1}{\alpha}}\)- approximation algorithm for the counterpart model with market selection. Our techniques are also applicable to an important class of covering problems.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arkin, E., Joneja, D., Roundy, R.: Computational complexity of uncapacitated multi-echelon production planning problems. Operations Research Letters 8, 61–66 (1989)
Balas, E.: The prize collection travelling salesman problem. Networks 19, 621–636 (1989)
Bárány, I., Van Roy, T.J., Wolsey, L.A.: Uncapacitated lot-sizing: the convex hull of solutions. Mathematical Programming Study 22, 32–43 (1984)
Bartal, Y., Leonardi, S., Spaccamela, A.M., Sgall, J., Stougie, L.: Multiprocessor scheduling with rejection. SIAM Journal on Discrete Mathematics 13, 64–78 (2000)
Bertsimas, D., Teo, C., Vohra, R.: On dependent randomized rounding algorithms. Operations Research Letters 25, 105–114 (1999)
Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.: A note on the prize collecting traveling salesman problem. Mathematical Programming 59, 413–420 (1993)
Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 642–651 (2001)
Geunes, J., Romeijn, H.E., Taaffe, K.: Requirements planning with pricing and order selection flexibility. To appear in Operations Research (2004)
Goemans, M.X.: Approximate solutions of hard combinatorial problems. In: Lecture notes in the schoolof ASHCOMP (1996)
Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM Journal on Computing 24, 296–317 (1995)
Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM 48, 274–296 (2001)
Krarup, J., Bilde, O.: Plant location, set covering and economic lot sizing: an O(mn) algorithm for structural problems. In: Numerische Methoden Bei Optimierungsaufgaben, vol. 3, pp. 155–180 (1977)
Levi, R., Roundy, R.O., Shmoys, D.B.: Primal-dual algorithms for deterministic inventory problems. Technical Report TR1042, ORIE Department, Cornell University (2004) (submitted)
Levi, R., Roundy, R.O., Shmoys, D.B.: Primal-dual algorithms for deterministic inventory problems. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 353–362 (2004)
Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location. In: Proceedings of 6th APPROX, pp. 229–242 (2002)
Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: Proceedings of 7th APPROX, pp. 129–140 (2003)
Pochet, Y., Wolsey, L.A.: Lot-sizing with constant batches: Formulation and valid inequalities. Mathematics of Operations Research 18, 767–785 (1993)
Levi, R., Roundy, R., Shmoys, D.: A constant approximation algorithm for the one-warehouse multi-retailer problem. Technical Report TR1408, ORIE Department, Cornell University (2004); Submitted, extended abstract will appear in SODA 2005 (2005)
Levi, R., Roundy, R., Shmoys, D.: A constant approximation algorithm for the one-warehouse multi-retailer problem (Extended Abstract). In: Proceedings of the 16th Annual SIAM-ACM Symposium on Discrete Algorithms (2005)
Shmoys, D.B.: The design and analysis of approximation algorithms: facility location as a case study. In: Hosten, S., Lee, J., Thomas, R. (eds.) Trends in Optimization. AMS Proceedings of Symposia in Applied Mathematics (2004) (to appear)
Shmoys, D.B., Swamy, C.: Stochastic optimization is (almost) as easy as deterministic optimization. In: Proceedings of the 45th Annual IEEE Symposium on the Foundations of Computer Science, 2004, pp. 228–237 (2004)
Shmoys, D.B., Swamy, C., Levi, R.: Facility location with service installation costs. In: Proceedings of the 15th Annual SIAM-ACM Symposium on Discrete Algorithms, pp. 1081–1090 (2004)
Wagner, H.M., Whitin, T.M.: Dynamic version of the economic lot sizing model. Management Science 5, 89–96 (1958)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Levi, R., Geunes, J., Romeijn, H.E., Shmoys, D.B. (2005). Inventory and Facility Location Models with Market Selection. In: Jünger, M., Kaibel, V. (eds) Integer Programming and Combinatorial Optimization. IPCO 2005. Lecture Notes in Computer Science, vol 3509. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496915_9
Download citation
DOI: https://doi.org/10.1007/11496915_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26199-5
Online ISBN: 978-3-540-32102-6
eBook Packages: Computer ScienceComputer Science (R0)