running-time complexity – Optimization Online

An Environmentally Sustainable Feasible Policy for Dynamic Lot Sizing Model with Remanufacturing and Separate Setup Costs: Time Complexity and Optimality

Published: 2025/04/25, Updated: 2026/01/12

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, where m ≥ 1, or manufacturing from raw materials, and in the model, we have separate setup costs for manufacturing and remanufacturing. As is widely known, remanufacturing is an environmental preferable choice compared … 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