APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES
Tim Nonner, Alexander Souza · Discrete Mathematics Algorithms and Applications · 2009
The objective of the classical Joint Replenishment Problem (JRP) is to minimize ordering costs by combining orders in two stages, first at some retailers, and then at a warehouse. These orders are needed to satisfy demands that appear over time at the retailers. We investigate the natural special case that each demand has a deadline until when it needs to be satisfied. For this case, we present a randomized 5/3-approximation algorithm. We moreover prove that JRP with deadlines is APX-hard. Finally, we extend the known hardness results by showing that JRP with linear delay cost functions is NP-hard, even if each retailer has to satisfy only three demands.