New Approximation Guarantees for the Inventory Staggering Problem

References

• Alon N, Spencer JH (2016) The Probabilistic Method, 4th ed. (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Alon N, Mellinger KE, Mubayi D, Verstraëte J (2012) The de Bruijn–Erdős theorem for hypergraphs. Designs Codes Cryptography 65(3):233–245.Crossref, Google Scholar
• Alon N, Duke RA, Lefmann H, Rödl V, Yuster R (1994) The algorithmic aspects of the regularity lemma. J. Algorithms 16(1):80–109.Crossref, Google Scholar
• Anily S (1991) Multi-item replenishment and storage problem (MIRSP): Heuristics and bounds. Oper. Res. 39(2):233–243.Link, Google Scholar
• Boctor FF (2010) Offsetting inventory replenishment cycles to minimize storage space. Eur. J. Oper. Res. 203(2):321–325.Crossref, Google Scholar
• Croot E, Huang K (2013) A class of random algorithms for inventory cycle offsetting. Internat. J. Oper. Res. 18(2):201–217.Crossref, Google Scholar
• Cygan M, Fomin FV, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized Algorithms (Springer, Cham, Switzerland).Crossref, Google Scholar
• Dadush D, Eisenbrand F, Rothvoss T (2025) From approximate to exact integer programming. Math. Programming 210(1):223–241.Crossref, Google Scholar
• Davenport H, Montgomery HL (2013) Multiplicative Number Theory, Graduate Texts in Mathematics, 2nd ed. (Springer, New York).Google Scholar
• Dubhashi DP, Panconesi A (2009) Concentration of Measure for the Analysis of Randomized Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Duke RA, Lefmann H, Rödl V (1995) A fast approximation algorithm for computing the frequencies of subgraphs in a given graph. SIAM J. Comput. 24(3):598–620.Crossref, Google Scholar
• Dusart P (2018) Explicit estimates of some functions over primes. Ramanujan J. 45:227–251.Crossref, Google Scholar
• Frank A, Tardos É (1987) An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7:49–65.Crossref, Google Scholar
• Gallego G, Queyranne M, Simchi-Levi D (1996) Single resource multi-item inventory systems. Oper. Res. 44(4):580–595.Link, Google Scholar
• Gallego G, Shaw D, Simchi-Levi D (1992) The complexity of the staggering problem, and other classical inventory problems. Oper. Res. Lett. 12(1):47–52.Crossref, Google Scholar
• Hall NG (1998) A comparison of inventory replenishment heuristics for minimizing maximum storage. Amer. J. Math. Management Sci. 18(3–4):245–258.Crossref, Google Scholar
• Hartley R, Thomas LC (1982) The deterministic, two-product, inventory system with capacity constraint. J. Oper. Res. Soc. 33(11):1013–1020.Crossref, Google Scholar
• Hartman A, Mullin RC, Stinson DR (1982) Exact covering configurations and Steiner systems. J. London Math. Soc. 2(2):193–200.Crossref, Google Scholar
• Hochbaum DS, Rao X (2019) The replenishment schedule to minimize peak storage problem: The gap between the continuous and discrete versions of the problem. Oper. Res. 67(5):1345–1361.Link, Google Scholar
• Hochbaum DS, Rao X (2020) A fully polynomial time approximation scheme for the replenishment storage problem. Oper. Res. Lett. 48(6):835–839.Crossref, Google Scholar
• Homer ED (1966) Space-limited aggregate inventories with phased deliveries. J. Indust. Engrg. 17(6):327.Google Scholar
• Hum S, Sharafali M, Teo C (2005) Staggering periodic replenishment in multivendor JIT environments. Oper. Res. 53(4):698–710.Link, Google Scholar
• Jackson P, Maxwell W, Muckstadt J (1985) The joint replenishment problem with a powers-of-two restriction. IIE Trans. 17(1):25–32.Crossref, Google Scholar
• Jansen K (2010) An EPTAS for scheduling jobs on uniform processors: Using an MILP relaxation with a constant number of integral variables. SIAM J. Discrete Math. 24(2):457–485.Crossref, Google Scholar
• Jansen K, Klein K, Verschae J (2020) Closing the gap for makespan scheduling via sparsification techniques. Math. Oper. Res. 45(4):1371–1392.Link, Google Scholar
• Kannan R (1987) Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3):415–440.Link, Google Scholar
• Lenstra HW (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
• Lokshtanov D (2009) New methods in parameterized algorithms and complexity. PhD thesis, University of Bergen, Norway.Google Scholar
• Muckstadt JA, Roundy RO (1993) Analysis of multistage production systems. Graves SC, Kan AHGR, Zipkin PH, eds. Handbooks in Operations Research and Management Science, vol. 4 (Elsevier, Amsterdam), 59–131.Google Scholar
• Muckstadt JA, Sapra A (2010) Principles of Inventory Management: When You Are Down to Four, Order More (Springer Science & Business Media, New York).Crossref, Google Scholar
• Murthy NN, Benton WC, Rubin PA (2003) Offsetting inventory cycles of items sharing storage. Eur. J. Oper. Res. 150(2):304–319.Crossref, Google Scholar
• Nisan N, Wigderson A (1994) Hardness vs randomness. J. Comput. System Sci. 49(2):149–167.Crossref, Google Scholar
• Niven I, Zuckerman HS, Montgomery HL (1991) An Introduction to the Theory of Numbers, 5th ed. (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Page E, Paul RJ (1976) Multi-product inventory situations with one restriction. J. Oper. Res. Soc. 27(4):815–834.Crossref, Google Scholar
• Reis V, Rothvoss T (2023) The subspace flatness conjecture and faster integer programming. Proc. 64th IEEE Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 974–988.Google Scholar
• Roundy R (1985) 98%-effective integer-ratio lot-sizing for one-warehouse multi-retailer systems. Management Sci. 31(11):1416–1430.Link, Google Scholar
• Roundy R (1986) A 98%-effective lot-sizing rule for a multi-product, multi-stage production/inventory system. Math. Oper. Res. 11(4):699–727.Link, Google Scholar
• Segev D (2026) Economic warehouse lot scheduling: Breaking the 2-approximation barrier. Preprint, submitted January 21, https://arxiv.org/abs/2601.15068.Google Scholar
• Simchi-Levi D, Chen X, Bramel J (2014) The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management, 3rd ed. (Springer Science & Business Media, New York).Crossref, Google Scholar
• Teo CP, Ou J, Tan KC (1998) Multi-item inventory staggering problems: Heuristics and bounds. Proc. 9th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 584–593.Google Scholar
• Zipkin PH (2000) Foundations of Inventory Management (McGraw-Hill, Boston).Google Scholar
• Zoller K (1977) Deterministic multi-item inventory systems with limited capacity. Management Sci. 24(4):451–455.Link, Google Scholar