Suppose you have N items with weights w$1,...,$ wN $0.$ Let $[$N $]=\{1,...,$ N $\}$ and for

any set S $[$N $],$ define w$($S$)=$ P

j in S wj $.$ In the problem SPLIT$-$EVEN, we are given such

a collection $\{$w$1,...,$ wN $\}$ and the goal is to partition $[$N $]$ into sets S$1,$ S$2$ and S$3$ so that

max$\{$w$($S$1),$ w$($S$2),$ w$($S$3)\}$ is minimized.

For this problem, we consider the following greedy strategy:

$1.$ Initialize sets S$1,$ S$2,$ S$3$ to be empty sets.

$2.$ For i $=1$ to N $,\{,$

$3.$ Let j in $\{1,2,3\}$ be such that w$($Sj $)$ has the least weight among S$1,$ S$2$ and S$3.$

$($ties can be broken arbitrarily$)$

$4.$ Add the ith item to the set Sj $\}.$

$5.$ Output the sets S$1,$ S$2$ and S$3.$

To analyze the performance, let OPT denote the cost of the best solution $$ i$.$e$.,$ OPT $=$

minJ$1,$J$2,$J$3$ max$\{$w$($J$1),$ w$($J$2),$ w$($J$3)\}$ where $($J$1,$ J$2,$ J$3)$ ranges over all partitions of $[$N $].$

$($a$)[10$ points$]$ Prove that OPT $1/3($P

j wj $)$ and OPT $$ maxj wj $.$

$($b$)[10$ points$]$ Assume without loss of generality that when our algorithm terminates, w$($S$1)=$

max$\{$w$($S$1),$ w$($S$2),$ w$($S$3)\}.$ Suppose $$ was the last index added to S$1.$ Prove that w$($S$1)$w$$

$1$

$3($PN

j$=1$ wj $).$

$($c$)[5$ points$]$ From $($a$)$ and $($b$),$ prove that w$($S$1)2$ OPT.