
Knapsack and Subset Sum with Small Items
Knapsack and Subset Sum are fundamental NPhard problems in combinatoria...
read it

Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time
Knapsack problems are among the most fundamental problems in optimizatio...
read it

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
In view of the undisputed success of neural networks and due to the rema...
read it

Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
One of the most fundamental problems in Theoretical Computer Science is ...
read it

Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Computing the convolution A⋆ B of two lengthn vectors A,B is an ubiquit...
read it

An exact, cachelocalized algorithm for the subquadratic convolution of hypercubes
Fast multidimensional convolution can be performed naively in quadratic ...
read it

Exact exponential algorithms for two poset problems
Partially ordered sets (posets) are fundamental combinatorial objects wi...
read it
Fast Algorithms for Knapsack via Convolution and Prediction
The knapsack 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 wellknown NPhard 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) dynamicprogramming solution for the knapsack problem might be the fastest in the worst case. In fact, solving the knapsack problem was shown to be computationally equivalent to the (, +) convolution problem, which is thought to be facing a quadratictime barrier. This hardness is in contrast to the more famous (+, ·) convolution (generally known as polynomial multiplication), that has an O(n n)time solution via Fast Fourier Transform. Our main results are algorithms with nearlinear running times (in terms of the size of the knapsack and the number of items) for the knapsack problem, if either the values or sizes of items are small integers. More specifically, if item sizes are integers bounded by , the running time of our algorithm is Õ((n+t)). If the item values are integers bounded by , our algorithm runs in time Õ(n+t). Best previously known running times were O(nt), O(n^2) and O(n) (Pisinger, J. of Alg., 1999).
READ FULL TEXT
Comments
There are no comments yet.