A 5/3Approximation Algorithm for Joint Replenishment with Deadlines
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, which significantly improves the best known approximation
ratio of 1.8 obtained by Levi and Sviridenko (APPROX’06). We moreover prove that JRP with deadlines is APX-hard, which is
the first such inapproximability result for a variant of JRP. 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.