  The \Problem{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 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 \Problem{knapsack} problem might be the fastest in the worst case. In
fact, solving the \Problem{knapsack} 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{$(+, \cdot)$ convolution} (generally known as
\Problem{polynomial multiplication}), that has an $O(n\log 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 \Problem{knapsack}
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 $\tilde O((n+t)\smax)$. If the item values are integers
bounded by $\vmax$, our algorithm runs in time $\tilde O(n+t\vmax)$. Best
previously known running times were $O(nt)$, $O(n^2\smax)$ and $O(n\smax\vmax)$
(Pisinger, J. of Alg., 1999).
