In an instance of the BALANCE problem, we are given $n$ items with positive integer weights

$w_1,$dots,$w_n,$ and an integer $k>1.$ We are required to assign each of the $n$ items to one of $k$ groups

$($indexed from $1$ to $k)$ in a way that minimizes the maximum, over all groups $j,$ of the total weight

assigned to group $j.$ The BALANCE problem is known to be NP$-$hard. A natural greedy heuristic for

the BALANCE problem proceeds in $n$ rounds as follows. Initially, no item is assigned to a group. In

round $i,1in,$ item $i$ is $($permanently$)$ assigned to a group with minimum total weight assigned

to it in the first $i-1$ rounds.

Example: Suppose $n=5,k=2,w_1=3,w_2=12,w_3=2,w_4=8,w_5=7,$ and that the greedy

heuristic assigns item $1$ to group $1.$ Then the greedy heuristic assigns item $2$ to group $2,$ items $3$

and $4$ to group $1,$ and item $5$ to group $2.$ For this solution, the maximum total weight assigned to

a single group is $12+7=19.$ Under an optimal solution, the maximum total weight assigned to a

single group is $12+3+2=17.$ End of example.

In the parts below, fix an instance I of BALANCE and let $Z$ denote the maximum total weight

assigned to a single group in some optimal solution to I.

$($a$)$ Let i belong to $\{1,$dots,$n\}$ and assume that in round $i,$ the greedy heuristic assigns

item $i($i$.$e$.,$ the item with weight $w_i)$ to group $j.$ Further assume that the total weight assigned

to group $j$ before round $i$ is $W.$ Prove that $Z$max$(w_i,W).$

$($b$)$ Make the same assumptions as in part $($a$).$ Prove that the total weight assigned

to group $j$ in the first i rounds is at most $2Z.$

$($c$)$ Briefly explain why the result of part $($b$)$ implies that the greedy heuristic finds

a solution to instance I where the total weight assigned to any group is at most $2Z.$