Academic
Publications
A 5/3Approximation Algorithm for Joint Replenishment with Deadlines

A 5/3Approximation Algorithm for Joint Replenishment with Deadlines,10.1007/978-3-642-02026-1_3,Tim Nonnerand,Alexander Souza

A 5/3Approximation Algorithm for Joint Replenishment with Deadlines  
BibTex | RIS | RefWorks Download
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.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.