<h2>Part A</h2>
1. (b)
2. (b)
3. (b)
4. (c)
<h2>Part B</h2>
1. Let us say that job $J_k$ has been assigned to machine $j$. This means that the load of the machine $j$ is at least $\ell_k$. Because the cost of is defined as the maximum of the load of all the machines, we know that the maximum is at least $\ell_k$.
2. Let $c$ be the cost. We know by definition that for any machine $j$:$$c\geq \sum_{i \in \{1,\dots,n\} \mid J_i\text{ has been assigned to machine }j}\ell_i$$Hence $$\sum_{j=1}^mc \geq \sum_{j=1}^m \sum_{J_i \in \{1,\dots,n\} \mid i\text{ has been assigned to machine }j}\ell_i$$and because every job gets assigned to exactly one machine we get$$\sum_{j=1}^mc \geq \sum_{i=1}^n \ell_i$$, or $$mc \geq \sum_{i=1}^n \ell_i$$$$mc \geq \sum_{i=1}^n \ell_i$$ or $$c \geq \frac{\sum_{i=1}^n \ell_i}{m}.$$
3. Assume that $j$ is the machine with the biggest load in the end and that $J_k$ is the last job added to that machine. Let $s$ the be the total load of machine $j$ minus $\ell_k$. We see that
   $$\text{ALG}=\ell_k+s \leq \ell_k +\frac{\sum_{i=1}^n\ell_i - \ell_k}{m} \leq c+c-\frac{c}{m} = (2-\frac{1}{m})c$$<h2>Part C</h2>
   1. One lower bound is $n$ and another is $\sum_{i}m_i^P$.
   2. $\frac{1+2p}{1+p}$ $2-\frac{1}{p+1}=\frac{p}{p+1}$
   3. $\frac{1+2p}{1+p}$
<h2>Part E</h2>
1. min $\sum_{j=1}^n\left(y_jf_j+\sum_{i=1}^m x_{ij}c_{ij}\right)$ s.t. $\sum_{i=1}^m x_{ij}\leq k_j\forall j$ $my_j\geq \sum_{i=1}^m x_{ij}\forall j$ $x_{ij},y_j\in \{0,1\}$
2. The same except $x_{ij},y_j\in\{0,1\}$.