Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918259850215424 |
|---|---|
| author | Sim, Chee-Khian |
| author_facet | Sim, Chee-Khian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_05017 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity Sim, Chee-Khian Computational Complexity Optimization and Control 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. |
| title | Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity |
| topic | Computational Complexity Optimization and Control |
| url | https://arxiv.org/abs/2412.05017 |