State the Bin Packing Problem $($BPP$)$ and explain in words how the Next Fit, First

Fit and First Fit Decreasing heuristics work. Run each of these three heuris$-$

tics on the following example: Let $b=1$ be the capacity of each bin and $L=$

$(\frac{1}{2},\frac{1}{7},\frac{1}{2},\frac{1}{4},\frac{1}{3},\frac{3}{4},\frac{1}{2}).$ Explain why First Fit Decreasing produces an optimal solution.

Consider the instance of the Symmetric Travelling Salesperson Problem $($STSP$)$

given in Figure $1.$ Run the following STSP heuristics on the instance:

$($a$)$ Greedy Algorithm $($give the order in which the edges are picked for the tour

and mention the edges which are not$),$

$($b$)$ Nearest Neighbour Heuristic starting from vertex $c($give the order in which

vertices are picked for the tour$),$

$($c$)$ Double Tree Heuristic $($describe every step of the heuristic$),$

$($d$)$ Christofides Heuristic $($describe every step of the heuristic$).$

Figure $1$: STSP instance.