Approximation Algorithms

FPTAS

Semidefinite Programming

Poly dep for knapsack

Citation Harvard University via Youtube

Harvard Lecture 12: Advanced Algorithms |

The setup is a knapsack of size W. We have n items with weights. w1 up to wn

Values V1 up to Vn

The goad is to pack the knapsack

To get FPTAS we need to find new values.

Run an O of n V Prime Algorithm. So What's any bound on V Prime?

V Prime is less than or equal to n times max. Less than or equal to N squared over Epson

Know OPT is the max Prime. The maximum value of the Vi Primes.