Approximately Counting Knapsack Solutions in Subquadratic Time

Weiming Feng, Ce Jin

We revisit the classic #Knapsack problem, which asks to count the Boolean points $(x_1,\dots ,x_n)\in \{0,1{\}}^n$ in a given half-space ${\sum }_{i=1}^n{W}_i{x}_i\le T$. This #P-complete pro…