= Greedy two-bin scheduling bound
{title2=$\operatorname{ALG}\leq\tfrac32\operatorname{OPT}$}
Put each successive item into a currently lighter bin. Before receiving weight $w_j$, that bin contains at most half the total weight already assigned, hence at most $(s-w_j)/2$, where $s$ is the overall total. Apply this to the last item in a finally heaviest bin to get $\operatorname{ALG}\leq s/2+w_{\max}/2$. Since $\operatorname{OPT}\geq\max(s/2,w_{\max})$, the approximation ratio is at most $3/2$. Ordered weights $1,1,2$ give loads $3,1$ rather than the optimal $2,2$, proving the bound is sharp. Its relative-error guarantee is $\varepsilon=1/2$.
Back to article page
