Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs

Parikshit Gopalan, Adam Klivans, Raghu Meka

We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with…