2018/11/30 by MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Bateni, MohammadHossein +5 · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1811.12554
openalex publication_date 2018/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The \Problemknapsack problem is a fundamental problem in combinatorial optimization. It has been studied extensively from theoretical as well as practical perspectives as it is one of the most well-known NP-hard problems. The goal is to pack a knapsack of size t with the maximum value from a collection of n items with given sizes and values. Recent evidence suggests that a classic O(nt) dynamic-programming solution for the \Problemknapsack problem might be the fastest in the worst case. In fact, solving the \Problemknapsack problem was shown to be computationally equivalent to the \Problem(min, +) convolution problem, which is thought to be facing a quadratic-time barrier. This hardness is in contrast to the more famous \Problem(+, ⋅) convolution (generally known as \Problempolynomial multiplication), that has an O(nlog n)-time solution via Fast Fourier Transform. Our main results are algorithms with near-linear running times (in terms of the size of the knapsack and the number of items) for the \Problemknapsack problem, if either the values or sizes of items are small integers. More specifically, if item sizes are integers bounded by \smax, the running time of our algorithm is O((n+t)\smax). If the item values are integers bounded by \vmax, our algorithm runs in time O(n+t\vmax). Best previously known running times were O(nt), O(n2\smax) and O(n\smax\vmax) (Pisinger, J. of Alg., 1999).