FPTAS for 1D knapsack

Dependencies:

1. Bin packing and Knapsack
2. Pseudo-polynomial time algorithm for 1D knapsack

There is an FPTAS for the knapsack problem. See Algorithm 3.2 in the book 'The Design of Approximation Algorithms' by Williamson and Shmoys.

The running time is $O(n^3/\epsilon)$.

Dependency for:

1. 1BP: FPTAS for config LP

Info:

• Depth: 2
• Number of transitive dependencies: 2

Transitive dependencies:

1. Bin packing and Knapsack
2. Pseudo-polynomial time algorithm for 1D knapsack