$($a$)$ Give an informal description of the Assignment Problem $($AP$).$ Provide an In$-$

teger Programming formulation of AP$.$ Explain the meaning of all parameters,

variables and constraints.

$($b$)$ Describe the greedy algorithm for AP$.$ What does it mean that the greedy

algorithm for $AP$ is of domination number $1?$

$($c$)$ Prove that the greedy algorithm for AP is of domination number $1.$

$($d$)$ Run the Greedy Algorithm on the instance of the STSP given in Figure $1.$

Show in which order the algorithm picks the edges for the tour. Now run

the Insertion Algorithm on this instance of the STSP starting from subtour

ABCA and inserting first $D$ and then $E.$ Which subtour do we obtain after

inserting $D$ and which tour do we obtain after inserting $E?$ Justify your

answers.