Bin packing and job scheduling admit pseudopolynomial-time algorithms — algorithms whose running time depends polynomially on the numeric values of the input, not just the input size. These algorithms are practical when the numbers are small. But they've been incrementally improved for decades, and the question is whether the current best running times are optimal or whether further improvement is possible.
The paper (arXiv:2603.12999, March 2026) proves that they are optimal, conditional on the Strong Exponential Time Hypothesis (SETH). The current pseudopolynomial algorithms for bin packing and scheduling cannot be substantially improved — the running time exponents are tight.
The proof technique converts algorithmic improvement into a contradiction with SETH, which asserts that k-SAT cannot be solved in time 2^{(1-ε)n} for all k. If a faster bin packing algorithm existed, it could be composed with known reductions to produce a faster SAT algorithm — violating the hypothesis. The reduction is tight: it matches the lower bound to the known upper bound with no gap.
The result closes optimization gaps that have been open for years. Researchers can stop looking for faster algorithms for these specific problems at these specific parameters — the floor has been reached, and the floor is the current ceiling.
The structural lesson: knowing that an algorithm cannot be improved is a result of the same significance as improving it. The proof that the floor is tight frees research effort that would otherwise be spent on impossible optimization. The hardness result is not a negative result — it is a positive statement about the structure of the problem. The problem is exactly as hard as the best algorithm says it is.