Section $4\mathrm{.}2\mathrm{.}2$ gives an allocation rule for knapsack auctions that is monotone, guarantees at least $50\%$ of the maximum

social welfare, and runs in polynomial time. Can we do better?

We first describe a classical fully polynomial$-$time approximation

scheme $($FPTAS$)$ for the knapsack problem. The input to the problem is item values v$1,...,$ vn$,$ item sizes w$1,...,$ wn$,$ and a knapsack

capacity W$.$ For a user$-$supplied parameter $>0,$ we consider the

following algorithm A$$; m is a parameter that will be chosen shortly.