A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem

Retsef Levi · ROBIN O. ROUNDY · David B. Shmoys · Maxim I. Sviridenko

100 citations0/0 files storedManagement Science

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Supply Chain and Inventory Management Complexity and Algorithms in Graphs Optimization and Search Problems

Abstract

Deterministic inventory theory provides streamlined optimization models that attempt to capture trade-offs in managing the flow of goods through a supply chain. We will consider two well-studied deterministic inventory models, called the one-warehouse multiretailer (OWMR) problem and its special case the joint replenishment problem (JRP), and give approximation algorithms with worst-case performance guarantees. That is, for each instance of the problem, our algorithm produces a solution with cost that is guaranteed to be at most 1.8 times the optimal cost; this is called a 1.8-approximation algorithm. Our results are based on an LP-rounding approach; we provide the first constant approximation algorithm for the OWMR problem and improve the previous results for the JRP.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 100 citations exist upstream.

References

1958Dynamic Version of the Economic Lot Size Model 1991A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time 1989Computational complexity of uncapacitated multi-echelon production planning problems 1973A Simple Continuous Review Deterministic One-Warehouse N-Retailer Inventory Problem 2002Effective Zero-Inventory-Ordering Policies for the Single-Warehouse Multiretailer Problem with Piecewise Linear Cost Structures

Cited by

2019Joint replenishment and carbon trading in fresh food supply chains 2014The warehouse-inventory-transportation problem for supply chains 2013Approximation Algorithms for the Stochastic Lot-Sizing Problem with Order Lead Times 2011The one-warehouse multi-retailer problem: reformulation, classification, and computational results 2019Inventory management for one warehouse multi-retailer systems with carbon emission costs 2009A Power-of-Two Ordering Policy for One-Warehouse Multiretailer Systems with Stochastic Demand 2015The submodular joint replenishment problem 2020

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.