Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 40 / 6

Let $z_i\in \{0,1\}$ indicate that item $i$ is placed in the first bin; otherwise it is placed in the second. The two-bin load balancing problem has the familiar mixed-integer formulationThe continuous variable $y$ becomes the maximum of the two bin loads at an optimum. A pure binary integer program, avoiding any integrality assumption on the weights or on $y$, is obtained by labelling a heavier bin as the first bin:The constraint ensures that the first load is at least the second, so the objective is their maximum. Every partition can be relabelled in this way, and every binary solution gives a partition. Thus this all-integer assignment formulation has exactly the original optimal value.

Use the relative-error approximation for minimization convention: an $\epsilon$-approximation returns a feasible solution of value $Y$ with $Y\le (1+\epsilon )Y^{\ast }$ on every instance, where $Y^{\ast }$ is the optimum. Equivalently the relative excess is at most $\epsilon$; the multiplicative-ratio convention reports $1+\epsilon$ instead.

Before item $j$ is assigned, the total load already placed is ${\sum }_{i<j}{w}_i$. The lighter of two bins has load at most half that total. Positivity of the weights givesChoose a bin attaining the final maximum load $Y$, and let $j$ be its last assigned item. No later item enters that bin, soEvery feasible schedule has $Y^{\ast }\ge s/2$ and $Y^{\ast }\ge w_{\max }$. HenceThe ordered weights $1,1,2$ make the greedy loads $1,1$ after two assignments and then $3,1$, regardless of how the final tie is resolved. The optimal partition has loads $2,2$. Thus the factor $3/2$ is attained, not merely a loose bound. We conclude the sharp greedy two-bin scheduling bound

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.