Question

Optimization PS(3) Problem:

Given a set of n program and three storage devices.

Let s_i be the amount of storage needed to store the i^th program. Let L be the storage capacity of each disk. Determine the maximum number of these n programs that can be stores on the three disks (without splitting a program over the disks).

Use the Approximation PS Algorithm given in the class for the PS(3) problem given above. Show that the following is true.

Let the approximation PS algorithm returns a number C, and let C^* be the optimal (maximum) number of programs that can be stores on the three disks.

(a) Show that the above approximation PS algorithm gives the performance ratio of C^* <= (C + 2) OR (C^* / C) <= (1 + 2 / C)

(b) Give an example that achieves the performance ratio of C^* = (C + 2).

Answer 1

Answer:

Note: It is calculated by the standard PS algorithm

Given:

Given data states the program is storing AT MOST 2 program lesser than the optimal solution

The PS algorithm approximation returning the C number

where the optimal value is C*

It is very obvious for showing the and L such that C*=(C+2)

Consider the 3 disk with capacity 6L

Hence the maximum number of programs can be stored into the disk and that can be considered as,

it states the is the MAXIMUM number of PROGRAMS that is stored in the disk

j is considered as the index value

It states that   and program j are accumulated in the first disk by applying approximation algorithm

By applying the equation ''i'' and ''íi''

At least the