Better approximation bounds for the joint replenishment problem

Abstrakt

We provide several new approximation results for the joint replenishment problem. In the offline case, we give an algorithm with ratio $\approx 1.791$, breaking the barrier of $1.8$.

In the online case, we show a lower bound of $\approx 2.754$ on the competitive ratio, improving the previous bound of $2.64$. We also study the online version with deadlines, for which we prove that the optimal competitive ratio is $2$.

Klíčová slova

• approximation algorithms
• online algorithms
• joint replenishment problem