Fast algorithms for knapsack via convolution and prediction

MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, Cliff Stein

Abstract

The Knapsack problem is a fundamental challenge in combinatorial optimization. While solvable in $O(nt)$ time via dynamic programming, fine-grained complexity suggests a quadratic barrier linked to $(\min, +)$ convolution. This paper introduces a novel "prediction technique" to bypass this barrier for instances with small item sizes ($s_{max}$) or values ($v_{max}$). By leveraging approximate solutions to accelerate exact $(\max, +)$ convolution, the authors achieve near-linear running times for several Knapsack variants and related problems like Tree Sparsity.

Introduction

The knapsack problem—maximizing the total value of items packed into a capacity $t$—is a cornerstone of combinatorial optimization. Despite being NP-hard, it is famously solvable in $O(nt)$ time using dynamic programming. However, recent developments in fine-grained complexity suggest that $O(nt)$ might be a fundamental limit, as solving Knapsack is computationally equivalent to $(\min, +)$ convolution. This problem is widely believed to have a "quadratic barrier," meaning improvements beyond $n^2$ are unlikely without major breakthroughs. This research addresses this challenge by bypassing the barrier for "moderate" instances where the maximum item size ($s_{max}$) or value ($v_{max}$) is small.

The Prediction Technique

The primary innovation of this work is the Prediction Technique, which accelerates $(\max, +)$ convolution when an approximate solution is available. This method proceeds in three stages:

  1. Reduction to Polynomial Multiplication: For small integer values, $(\max, +)$ convolution is reduced to standard $(+, \cdot)$ convolution (polynomial multiplication), solvable in near-linear time via Fast Fourier Transforms (FFT).
  2. Handling Small Distortion: If the difference between the sum of two elements and the optimal convolution result is bounded by an error $e_{max}$, the vectors can be transformed into a small range suitable for FFT-based approaches.
  3. Prediction via Uncertain Solutions: By using an "uncertain solution"—a set of intervals containing the optimal indices—the algorithm decomposes large convolution problems into many smaller "small distortion" subproblems.

For small item sizes, a randomized bucket-based approach is employed. Items are distributed into buckets, solved individually, and merged efficiently using the prediction technique and Bernstein’s inequality.

Key Results and Complexity Bounds

The paper establishes several new complexity bounds that significantly outperform previous state-of-the-art results. For instance, when item sizes are bounded by $s_{max}$, the algorithm achieves a running time of $\tilde{O}((n+t)s_{max})$, a substantial improvement over the previous $O(n^2 s_{max})$.

Table of improved running times for various knapsack settings compared to previous work.

As shown in the table above, the improvements extend to variants with unlimited or given multiplicities, providing the first strongly polynomial time algorithms for these cases.

Beyond the knapsack problem, these techniques provide a unified framework for solving related combinatorial problems. The prediction technique is shown to be a versatile tool for problems like Tree Sparsity and Tree Separability.

Hierarchy of problems and their complexity bounds under the proposed framework.

The hierarchy illustrates how bounded convolution serves as a primitive for more complex problems. While many problems see significant speedups, 0/1 Tree Sparsity remains a challenging open question for achieving truly linear-time solutions.

Conclusion

This work demonstrates that the "quadratic barrier" for $(\min, +)$ convolution is sensitive to the range of input values. By leveraging high-quality "predictions" (such as those from greedy strategies) and shifting problems into a space where FFT-based tools are applicable, the authors achieve near-linear performance for critical classes of the Knapsack problem. Future work remains in finding deterministic versions of the randomized bounds and addressing the general case where values are arbitrarily large.

Summary updated

BibTeX
@inproceedings{bateni2018fast,
  author = {MohammadHossein Bateni and MohammadTaghi Hajiaghayi and Saeed Seddighin and Cliff Stein},
  title = {{Fast algorithms for knapsack via convolution and prediction}},
  booktitle = {STOC},
  year = {2018},
  doi = {10.1145/3188745.3188876},
}
Figure