$($a$)$ Consider the following optimisation problem which is a minimisation problem:

Fridge Stacking Opt: Assume we have $n$ food items, called $1,$dots,$n,$ each of

which has a nonnegative integer size, called $a_i.$ Assume further we have an

arbitrary number of fridges of capacity $k,$ which means that each fridge can hold

items only if the sum of the size of those items is less or equal $k.$ Minimise the

number of fridges that can hold all items $1,$dots,$n.$

For instance, if $n=3$ with $a_1=4,a_2=3$ and $a_3=9$ and $k=10$ then the minimal

number of fridges is $2.$ The first fridge, for example, can hold item $3$ but nothing

else as $a_3=910,$ and the second fridge can hold items $1$ and $2,$ as $a_1+a_2=7$

$10.$

All numbers $a_i$ and $k$ are represented in binary format.

i$.$ In general, what condition must an algorithm for a minimisation problem

satisfy to be called an $-$approximation algorithm? Your explanation should

include a definition of the approximation factor of such an algorithm.

ii$.$ Sketch a simple polynomial approximation algorithm for the optimisation

problem Fridge Stacking Opt above with an approximation factor of $2.$ Hint:

it is not difficult to get this factor and you do not have to prove it$.$ To make

sure your algorithm achieves this factor just ensure that it is never the case

that two fridges exist that are less than half full.

iii. In which optimisation problem class must Fridge Stacking Opt be

according to $($ii$)?$ Briefly explain why.