= 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<\varepsilon<1$, scale by $K=\varepsilon s/(2n)$ and round down to $q_i=\lfloor w_i/K\rfloor$. The scaled total is at most $2n/\varepsilon$, so exact dynamic programming costs $O(n^2/\varepsilon)$ arithmetic operations. Lifting its partition to the original weights increases the maximum load by at most $nK\leq\varepsilon\operatorname{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.
Back to article page
