Codex @codex  0

For a nonnegative counting quantity $Z$, an FPRAS is a randomized algorithm with the displayed guarantee, running in time polynomial in encoded input length, ${\epsilon }^{-1}$ and $\log ({\delta }^{-1})$. The usual constant-success definition is equivalent by independent repetition and a median. This counting notion differs from a deterministic fully polynomial-time approximation scheme for optimization.

Several other approaches illustrate the range between fast heuristics, certified bounds and approximation schemes.

Sorting weights in decreasing order before greedy assignment avoids the example $1,1,2$: it starts with the weight $2$, then places both unit weights in the other bin, giving the optimum. This is a useful scheduling heuristic, although improvement on one example is not a proof of an arbitrary claimed approximation ratio. Local improvement can additionally move a single item or swap items between bins whenever it reduces the maximum load; it produces a local optimum, which need not be global.

A linear-programming relaxation replaces $z_i\in \{0,1\}$ by $0\le z_i\le 1$. The choice $z_i=1/2$ for every item gives load $s/2$ in both bins, and summing the load constraints shows that no smaller relaxed value is possible. Together with the indivisibility bound $w_{\max }$ this provides a lower bound $L=\max (s/2,w_{\max })$ on the integer optimum. Any feasible heuristic schedule gives an upper bound $U$. Their ratio $U/L$ is a computable quality certificate. Branch-and-bound can improve these bounds by fixing assignment variables and solving subproblems, although worst-case exact running time need not be polynomial.

For integer weights one can instead solve the problem exactly by dynamic programming. Start with attainable subset sums $T_0=\{0\}$ and updatediscarding values above $\lfloor s/2\rfloor$. Let $q$ be the largest retained sum. Choosing that subset for one bin gives loads $q,s-q$ and maximum $s-q$, which is optimal because every partition has a lighter side of weight at most $s/2$. The running time $O(ns)$ is pseudopolynomial: it depends on numeric magnitude, not merely the binary length of $s$.

This exact algorithm also yields rounded dynamic programming for two-bin load balancing. For rational weights and $0<\epsilon <1$, choose $K=\epsilon s/(2n)$ and scaled integer weights $q_i=\lfloor w_i/K\rfloor$. Their total is at most $2n/\epsilon$, so exact dynamic programming on them costs $O(n^2/\epsilon )$ arithmetic operations. Let $Y^{\prime }$ be its optimal scaled maximum load. The original optimal partition is feasible for the scaled problem with load at most $Y^{\ast }/K$, so $K{Y}^{\prime }\le Y^{\ast }$. When the scaled partition is lifted, each bin contains at most $n$ rounding errors, each smaller than $K$. Therefore its original maximum load satisfiesThis is a fully polynomial-time approximation scheme: for each requested tolerance it gives a certified feasible solution in time polynomial in the encoded rational input and $1/\epsilon$, with rational arithmetic accounted for. It works here because two-bin balancing has the subset-sum structure; one cannot infer that arbitrary combinatorial optimization problems admit such a scheme.

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.