I need to solve the multiple-choice knapsack problem for a very large input size ($\approx 10,000,000$). What is best way to practically do this? I've seen some papers describing FPTAS (=Fully Polynomial time Approximation Scheme) algorithms to it (for example - Improved Fully Polynomial time Approximation Scheme for the 0-1 Multiple-choice Knapsack Problem), but I didn't find any implementations, oddly enough.

I'm not sure as to how practical those papers are and whether it's recommended to actually implement one of those papers myself. Perhaps there are implemenatations that I've missed? If no, do you think I should implement one myself?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.