A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem

References

• Arkin E., Joneja D., Roundy R. Computational complexity of uncapacitated multi-echelon production planning problems. Oper. Res. Lett. (1989) 8:61–66Crossref, Google Scholar
• Bárány I., Van Roy T. J., Wolsey L. A. Uncapacitated lot-sizing: The convex hull of solutions. Math. Programming Stud. (1984) 22:32–43Crossref, Google Scholar
• Bertsimas D., Teo C., Vohra R. On dependent randomized rounding algorithms. Oper. Res. Lett. (1999) 25:105–114Crossref, Google Scholar
• Chan L. M. A., Muriel A., Shen Z.-J. M., Simchi-Levi D., Teo C.-P. Effective zero-inventory-ordering policies for the single-warehouse multiretailer problem with piecewise linear cost structures. Management Sci. (2000) 48:1446–1460Link, Google Scholar
• Federgruen A., Tzur M. A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(n log n) or O(n) time. Management Sci. (1991) 37:909–925Link, Google Scholar
• Federgruen A., Tzur M. Time-partitioning heuristics: Application to one warehouse, multi-item, multi-retailer lot-sizing problems. Naval Res. Logist. (1999) 46:463–486Crossref, Google Scholar
• Feige U. A threshold of ln(n) for approximating set-cover. J. ACM (1998) 45:634–652Crossref, Google Scholar
• Jain K., Vazirani V. V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM (2001) 48:274–296Crossref, Google Scholar
• Jin Y., Muriel A. Single-warehouse multi-retailer inventory systems with full truckload shipments. (2005) . Working paper, University of Massachusetts, AmherstGoogle Scholar
• Krarup J., Bilde O. Plant location, set covering and economic lot sizing: An O(mn) algorithm for structural problems. Numerische Methoden bei Optimierungsaufgaben (1977) 3:155–180Crossref, Google Scholar
• Levi R., Sviridenko M., Díaz J., Jansen K., Rolim J. D. P., Zwick U. Improved approximation algorithm for the one-warehouse multi-retailer problem. Approximation Randomization, and Combinatorial Optimization Algorithms and Techniques (2006) (Springer-Verlag, New York) 188–199Crossref, Google Scholar
• Levi R., Roundy R. O., Shmoys D. B. Primal-dual algorithms for deterministic inventory problems. Proc. 36th Annual ACM Sympos. Theory Comput. (2004) (ACM, New York) 353–362Crossref, Google Scholar
• Levi R., Roundy R. O., Shmoys D. B. Primal-dual algorithms for deterministic inventory problems. Math. Oper. Res. (2006) 31:267–284Link, Google Scholar
• Levi R., Shmoys D. B., Roundy R. O. A constant approximation algorithm for the one-warehouse multi-retailer problem. Proc. 15th Annual SIAM-ACM Sympos. Discrete Algorithms (2005) (SIAM, Philadelphia) 365–374Google Scholar
• Pochet Y., Wolsey L. A. Lot-sizing with constant batches: Formulation and valid inequalities. Math. Oper. Res. (1993) 18:767–785Link, Google Scholar
• Schwarz L. B. A simple continuous review deterministic one-warehouse N-retailer inventory problem. Management Sci. (1973) 19:555–566Link, Google Scholar
• Shen Z.-J., Simchi-Levi D., Teo C.-P. Approximation algorithms for the single-warehouse multi-retailer problem with piecewise linear cost structures. (2002) . http://citeseer.ist.psu.edu/439759.htmlGoogle Scholar
• Shen Z.-J., Simchi-Levi D., Teo C.-P., Zhang J. Approximate solutions to logistical planning problems in one-warehouse multi-retailer systems. (2007) . Working paper, University of California, BerkeleyGoogle Scholar
• Shmoys D. B., Hosten S., Lee J., Thomas R. The design and analysis of approximation algorithms: Facility location as a case study. Trends in Optimization. AMS Proccedings of Symposia in Applied Mathematics (2004) (AMS, Providence, RI) 85–98Crossref, Google Scholar
• Shmoys D. B., Tardos E., Aardal K. I. Approximation algorithms for facility location problems. Proc. 29th Annual ACM Sympos. Theory Comput. (1997) (ACM, New York) 265–274Google Scholar
• Wagner H. M., Whitin T. M. Dynamic version of the economic lot sizing model. Management Sci. (1958) 5:89–96Link, Google Scholar