arXiv preprint ·
Critical-state algorithms for lot sizing with all-units discounts and variable inventory bounds
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study deterministic single-item lot sizing with all-units quantity discounts, linear holding costs, and time-varying end-of-period inventory bounds. Unit prices may vary arbitrarily over time. For one common positive discount threshold, we give an exact algorithm requiring $O(n^3)$ arithmetic operations and $O(n^2)$ working space, including recovery of an optimal purchase plan. The method combines a critical-state theorem in cumulative-purchase coordinates with two prefix-minimum scans per dynamic-programming layer. The structural argument accommodates downward price discontinuities and distinguishes prescribed from free terminal inventory. With a fixed global set of $m$ positive threshold values, the bounds become $O_m(n^{m+2})$ time and $O_m(n^{m+1})$ space. Period-specific thresholds admit the same exact construction, but its state set can be exponential. For commensurate flow data, an inventory-lattice implementation takes $O(PW)$ time, where $P$ is the total number of price tiers and $W$ is the largest inventory-lattice width. We also derive a conditional optimality certificate from a monotone one-threshold relaxation; this certificate does not imply a near-linear worst-case algorithm for arbitrary prices. Exact-arithmetic implementations are checked against exhaustive inventory dynamic programs and tier-enumeration linear programs. An illustrative timing study identifies settings in which the lattice implementation is preferable.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Competitive Online Clustering with Movement Cost
Near-Linear Time Maximum Clique in Circular Arc Graphs
On the Metric Distortion of the Minimum Spanning Tree Problem
Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
Online geometric matching and segments block points
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.