Multistage lot sizing problems via randomized rounding

We study the classical multistage lot sizing problem that arises in distrib ution and inventory systems. A celebrated result in this area is the 94% an d 98% approximation guarantee provided by power-of-two policies. In this pa per, we propose a simple randomized rounding algorithm to establish these p erformance bounds. We use this new technique to extend several results for the capacitated lot sizing problems to the case with submodular ordering co st. For the joint replenishment problem under a fixed base period model, we construct a 95.8% approximation algorithm to the (possibly dynamic) optima l lot sizing policy. The policies constructed are stationary but not necess arily of the power-of-two type. This shows that for the fixed based plannin g model, the class of stationary policies is within 95.8% of the optimum, i mproving on the previously best known 94% approximation guarantee.