This problem shows how to design a Polynomial Time Approximation Scheme $($PTAS$)$ for

the knapsack problem. For any $lon>0,$ the PTAS will give a $(1-lon)-$approximation in at most

$f(lon)n^{g(lon)}$ time. Thus, we can trade runtime for approximation accuracy.

a$)$ Assume that $v_i<mi\; id="EditorElement\_1191788"></mi><mi\; id="EditorElement\_1191790">l</mi><mi\; id="EditorElement\_1191792">o</mi><mi\; id="EditorElement\_1191794">n</mi><mi\; id="EditorElement\_1191796">*</mi><mi\; id="EditorElement\_1191798">O</mi><mi\; id="EditorElement\_1191800">P</mi><mi\; id="EditorElement\_1191802">T</mi>$ for all items $i.$ Show that Greedy is a $(1-lon)-$approximation.

$[$Hint: Use $(1)$ from problem $1$ b$).]$

b$)$ Assume that we know OPT. Let $H=\{i|v_{i}lon*OPT\},$ be the set of 'high' valued

items, and $L=\{i|v_i<mi\; id="EditorElement\_1191451"></mi><mi\; id="EditorElement\_1191453">l</mi><mi\; id="EditorElement\_1191455">o</mi><mi\; id="EditorElement\_1191457">n</mi><mi\; id="EditorElement\_1191459">*</mi><mi\; id="EditorElement\_1191461">O</mi><mi\; id="EditorElement\_1191463">P</mi><mi\; id="EditorElement\_1191465">T</mi><mi\; id="EditorElement\_1191467">\}</mi>$ be the 'low' valued items. Observe that the optimal

subset contains no more than $\frac{1}{}$lon items from $H,$ otherwise OPT would be larger.

Assuming that we know OPT, consider the following approximation algorithm.

i$)$ Try each subset SsubeH with size $|S|\frac{1}{}$lon and $W(S)W.$

ii$)$ For any subset $S,$ let $G(S)$ be the output of Greedy using items of $L$ with remain$-$

ing weight $W-W(S).$

iii$)$ Return the best result, maxV$(SG(S)).$

Show that the above algorithm is a $(1-lon)-$approximation.

c$)$ Assuming that we know OPT, what is the runtime of the algorithm in part b$)?$ You

can assume $\frac{1}{}$ is an integer, and you can use crude bound on the number of subsets

$S$ tried in line i$).$

d$)$ Of course we don't know OPT. Explain how we can overcome this limitation$.$