  The Joint Replenishment Problem (JRP) deals with optimizing shipments of
goods from a supplier to retailers through a shared warehouse. Each shipment
involves transporting goods from the supplier to the warehouse, at a fixed cost
C, followed by a redistribution of these goods from the warehouse to the
retailers that ordered them, where transporting goods to a retailer $\rho$ has
a fixed cost $c_\rho$. In addition, retailers incur waiting costs for each
order. The objective is to minimize the overall cost of satisfying all orders,
namely the sum of all shipping and waiting costs.
  JRP has been well studied in Operations Research and, more recently, in the
area of approximation algorithms. For arbitrary waiting cost functions, the
best known approximation ratio is 1.8. This ratio can be reduced to 1.574 for
the JRP-D model, where there is no cost for waiting but orders have deadlines.
As for hardness results, it is known that the problem is APX-hard and that the
natural linear program for JRP has integrality gap at least 1.245. Both results
hold even for JRP-D. In the online scenario, the best lower and upper bounds on
the competitive ratio are 2.64 and 3, respectively. The lower bound of 2.64
applies even to the restricted version of JRP, denoted JRP-L, where the waiting
cost function is linear.
  We provide several new approximation results for JRP. In the offline case, we
give an algorithm with ratio 1.791, breaking the barrier of 1.8. In the online
case, we show a lower bound of 2.754 on the competitive ratio for JRP-L (and
thus JRP as well), improving the previous bound of 2.64. We also study the
online version of JRP-D, for which we prove that the optimal competitive ratio
is 2.
