Question:

Optimization PS $(k)$ Proble m: Given a set of $n$ program and $k$ storage devices $($disks$).$ Let $s_i$ be

the length $($amount of storage$)$ needed to store the $i^{th}$ program. Let $L$ be the storage capacity of

each storage device. Determine the maximum number of these $n$ programs that can be stored on

$k$ storage devices $($without splitting a program over the storage devices$).$

Use the Approximation PS Algorithm $($smallest$-$program$-$first$)$ covered in the class for the PS $(k)$

problem given above.

$($a$)(10$ pts$)$ Let the approximation PS algorithm returns a number $C,$ and let $C^{**}$ be the optimal

$($maximum$)$ number of programs that can be stored on the $k$ disks. Show that the above

approximation PS algorithm gives the performance ratio of $C^{**}(C+k-1).$