Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity
CK Sim - arXiv preprint arXiv:2412.05017, 2024 - arxiv.org
arXiv preprint arXiv:2412.05017, 2024•arxiv.org
In this note, we polynomially reduce an instance of the partition problem to a dynamic lot
sizing problem, and show that solving the latter problem solves the former problem. By
solving the dynamic program formulation of the dynamic lot sizing problem, we show that the
instance of the partition problem can be solved with pseudo-polynomial time complexity.
Numerical results on solving instances of the partition problem are also provided using an
implementation of the algorithm that solves the dynamic program. We conclude by …
sizing problem, and show that solving the latter problem solves the former problem. By
solving the dynamic program formulation of the dynamic lot sizing problem, we show that the
instance of the partition problem can be solved with pseudo-polynomial time complexity.
Numerical results on solving instances of the partition problem are also provided using an
implementation of the algorithm that solves the dynamic program. We conclude by …
In this note, we polynomially reduce an instance of the partition problem to a dynamic lot sizing problem, and show that solving the latter problem solves the former problem. By solving the dynamic program formulation of the dynamic lot sizing problem, we show that the instance of the partition problem can be solved with pseudo-polynomial time complexity. Numerical results on solving instances of the partition problem are also provided using an implementation of the algorithm that solves the dynamic program. We conclude by discussing polynomial time solvability of the partition problem through further observation on the dynamic program formulation of the dynamic lot sizing problem.
arxiv.org