Two-bin load balancing (${\min }_S\max \{{\sum }_{i\in S}{w}_i,{\sum }_{i\notin S}{w}_i\}$)

Partition positive item weights into two bins to minimize the heavier total. The optimum is at least both half the total weight and the largest individual weight. This is two-machine makespan minimization, rather than the version of bin packing that minimizes the number of fixed-capacity bins.

For integer weights, subset-sum dynamic programming finds the greatest achievable total at most $s/2$ in time $O(ns)$, where $s$ is the total weight. For rational weights and $0<\epsilon <1$, scale by $K=\epsilon s/(2n)$ and round down to $q_i=\lfloor w_i/K\rfloor$. The scaled total is at most $2n/\epsilon$, so exact dynamic programming costs $O(n^2/\epsilon )$ arithmetic operations. Lifting its partition to the original weights increases the maximum load by at most $nK\le \epsilon \mathrm{OPT}$. Thus it is a fully polynomial-time approximation scheme for this two-bin problem. Bit complexity also accounts for the rational input and epsilon encodings.

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 $\mathrm{ALG}\le s/2+w_{\max }/2$. Since $\mathrm{OPT}\ge \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 $\epsilon =1/2$.