CS 789 THEORY SEMINAR [home]

Speaker: Retsef Levi
Affiliation: ORIE, Cornell University
Date: Monday, September 29, 2003
Title: Improved Approximation Algorithm for The Joint Replenishment Problem

Abstract:

We consider the joint replenishment problem (JRP) in discrete time, with a finite horizon and deterministic time-dependent demand. For each of N items and T time periods, we have a given demand that must be satisfied on time.  In each time period we can order any subset of the items, paying a joint fixed cost in addition to an individual fixed cost for each item ordered.  We can also hold inventory while incurring an item-dependent linear holding cost. The goal is to find a policy that satisfies all demands on time and minimizes the overall fixed and holding cost. This classical deterministic inventory model is known to be NP-hard; many heuristics for finding optimal and near-optimal solutions have been developed. We will show how LP-based techniques yield efficient approximation algorithms with constant performance guarantees, significantly improving on previously known results. In particular, we give a novel primal-dual algorithm that builds upon and extends some of the ideas and techniques recently applied to facility location problems. Surprisingly, the algorithm can be modified to provide optimal and near-optimal solutions to other classical inventory models such as the 1-item lot-sizing problem and the assembly problem.

This is joint work with Robin Roundy and David Shmoys