An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912943851962368 |
|---|---|
| author | Papadopoulos, Kleitos |
| author_facet | Papadopoulos, Kleitos |
| contents | This paper addresses the single-item lot sizing problem with a 1-breakpoint all-units quantity discount in a monotonic setting where the purchase prices are non-increasing over the planning horizon. For this case, we establish several novel properties of the optimal solution and develop a hybrid dynamic programming approach that maintains a compact representation of the solution space by storing only essential information about the states and using linear equations for intermediate values. Our algorithm runs in \(O(n\log n)\) time, where \(n\) denotes the number of periods. Our result is an improvement over the previous state-of-the-art algorithm, which has an \(O(n^2)\) time complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_11368 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices Papadopoulos, Kleitos Data Structures and Algorithms This paper addresses the single-item lot sizing problem with a 1-breakpoint all-units quantity discount in a monotonic setting where the purchase prices are non-increasing over the planning horizon. For this case, we establish several novel properties of the optimal solution and develop a hybrid dynamic programming approach that maintains a compact representation of the solution space by storing only essential information about the states and using linear equations for intermediate values. Our algorithm runs in \(O(n\log n)\) time, where \(n\) denotes the number of periods. Our result is an improvement over the previous state-of-the-art algorithm, which has an \(O(n^2)\) time complexity. |
| title | An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.11368 |