Time Complexity and Optimality of Inventory and Production Policies for a Dynamic Lot Sizing Model with Remanufacturing and Separate Setup Costs

In this paper, we consider a dynamic lot sizing model with remanufacturing having m types of cores. The model also allows manufacturing. We consider separate setup costs for manufacturing and remanufacturing in our model. It is conjectured in [15], with reference to [18], that finding an optimal policy to the model when there is separate … Read more

Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time

We propose a randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality, the algorithm adaptively samples state transitions and makes exponentiated primal-dual updates. We show that it finds an ε-optimal policy using nearly-linear running time in the worst case. For Markov decision processes that … Read more