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, Updated: 2025/05/23

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

We consider a dynamic lot sizing model in which end products to satisfy demands are obtained by remanufacturing m types of cores or manufacturing from raw materials. We consider separate setup costs for manufacturing and remanufacturing in our model. It is conjectured in [21], with reference to [24], that finding an optimal policy to the … 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