running-time complexity – Optimization Online

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

Published: 2025/04/25

Dynamic Programming, Production and Logistics Dynamic lot sizing model, Inventory and production policies, remanufacturing system, running-time complexity

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

Published: 2017/04/05, Updated: 2017/09/13

Mengdi Wang

Dynamic Programming, Linear Programming duality, linear programming, markov decision processes, primal-dual algorithms, randomized algorithm, running-time complexity, stochastic approximation

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