Rounded dynamic programming for two-bin load balancing

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.