Fractional Relaxation and the Knapsack Integrality Gap

Two problems share a name and differ by one word. Fractional knapsack allows an item to be taken in part; 0/1 knapsack does not. The fractional version is solved optimally by sorting on value density and filling greedily, in $O(n \log n)$. The 0/1 version is NP-hard, and no greedy rule solves it. The gap between them is not a gap in cleverness but a gap in the shape of the feasible region, and measuring it precisely is the cleanest introduction to linear relaxations and integrality gaps.

The relaxation that greedy solves exactly

Write the 0/1 problem as an integer program. Items $1..n$ have weights $w_i$, values $v_i$, capacity $W$:

$$ \max \sum_i v_i x_i \quad \text{s.t.} \quad \sum_i w_i x_i \le W, \quad x_i \in {0,1} $$

Relaxing $x_i \in {0,1}$ to $0 \le x_i \le 1$ gives the fractional problem, a linear program. Its optimal solution has a specific shape, and the shape is forced by the constraints rather than discovered by a search.

Sort items by density $v_i / w_i$ descending. Take items in that order until the next one does not fit, then take the fraction of it that fills the capacity exactly. This is optimal, and the argument is an exchange: if an optimal solution leaves capacity unused while some item is taken at a fractional value below 1, it can increase that fraction. If it takes a lower-density item while leaving a higher-density item partly untaken, swapping a unit of weight between them does not increase total weight and does not decrease value. Repeating these two exchanges converges on the density-ordered solution.

The linear program’s structure explains why. Its feasible region is a simplex slice: the single constraint $\sum w_i x_i \le W$ together with the bounds defines a polytope whose vertices have at most one coordinate strictly between 0 and 1. An optimal solution of a linear program is attained at a vertex, so the fractional solution has at most one split item. Greedy finds that vertex directly. No search is needed because the vertex has a closed-form description.

Where the integrality gap appears

The integer optimum can be much smaller than the fractional optimum, and the worst ratio is exactly 2.

For the upper bound, let $S$ be the set of items the fractional optimum takes whole, with value $V$ and weight at most $W$, and let $j$ be the single fractional item, taken at fraction $f$. Then $V$ is achievable by an integral solution, so $\mathrm{OPT} \ge V$. Also $\mathrm{OPT} \ge v_j$, because $j$ alone fits: its weight is at most $W$ since it was taken fractionally. Hence

$$ \mathrm{LP} = V + f,v_j \le V + v_j \le 2,\mathrm{OPT} $$

For the lower bound, take capacity $W = 1$, an item $A$ of weight $\varepsilon$ and value 1, and an item $B$ of weight 1 and value 1. The fractional optimum takes $A$ whole and $B$ at fraction $1 - \varepsilon$, for value $2 - \varepsilon$. Every integral solution takes either $A$ or $B$ but not both, since $\varepsilon + 1 > 1$, so the integer optimum is 1. The ratio approaches 2 as $\varepsilon$ approaches 0. The gap is not an artifact of the bound; it is attained.

This is a statement about the relaxation, not about any particular algorithm. It says that any method that reasons from the fractional bound alone cannot certify better than a factor of 2.

The greedy algorithm’s own factor

A natural integral algorithm follows the fractional rule but stops at the first item that does not fit. Its ratio is at least $1/2$, and the bound is tight.

Let $g$ be the value the greedy rule obtains, let $S$ be the items it takes, and let $j$ be the first item it rejects, of value $v_j$. The fractional optimum is at most $g + v_j$, by the same vertex argument. If $v_j \le g$, then $\mathrm{LP} \le 2g$ and, since $\mathrm{OPT} \le \mathrm{LP}$, the ratio is at least $1/2$. If $v_j > g$, then $j$ alone is worth more than everything greedy took, so taking $j$ alone is a better solution than greedy’s; a variant that compares the greedy set against the single best item therefore achieves $\max(g, v_j) \ge \mathrm{LP}/2$.

The tight instance has capacity 1, an item $A$ of weight $1/2 + \varepsilon$ and value $(1/2 + \varepsilon)(1 + \delta)$, and two items $B$, $C$ of weight $1/2$ and value $1/2$ each. $A$ has the highest density, so greedy takes it and then has $1/2 - \varepsilon$ capacity left, into which neither half fits. Greedy’s value is about $1/2$; the optimum is $B$ together with $C$, worth 1. As $\varepsilon$ and $\delta$ shrink, the ratio approaches $1/2$.

The failure is exactly the failure of the exchange argument: replacing $A$ in an optimal solution by the two halves is infeasible, and no repair preserves value. In matroid terms from the matroid criterion, the feasible sets violate the exchange axiom: ${B, C}$ and ${A}$ are both maximal, at sizes 2 and 1.

Tightening by local repair

The 1/2 bound is what the density rule alone gives. Spending more computation improves the result, in ways that do not follow from the exchange argument.

Core-based reduction. Items far from the break density rarely take part in an optimal solution’s distinguishing decisions. Fixing the greedy solution and solving exactly on a small “core” of items near the break density is the standard refinement, and its price is that the worst-case guarantee is harder to state than the 1/2 of the simple rule. The technique behaves as a heuristic with a fallback, not as a uniform guarantee.

Meet in the middle. Split the items in half, enumerate all $2^{n/2}$ subsets of each half, discard infeasible ones, and merge the two lists by weight with a two-pointer scan. This solves the problem exactly in $O(2^{n/2})$ time and $O(2^{n/2})$ space, which is exponential but with a much smaller base than $2^n$, and it is tractable for instances of a few dozen items.

Scaling values to reach within a factor

The 0/1 problem has a pseudo-polynomial dynamic program: let $P = \sum v_i$ and compute, for each value target $p$, the minimum weight of a subset achieving value at least $p$. The table has $P$ columns and the running time is $O(nP)$, polynomial in the numeric value of the input rather than in its bit length. That is why knapsack is only weakly NP-hard: the hardness depends on values being encoded in binary.

Value scaling turns the pseudo-polynomial algorithm into an approximation scheme. Choose $K = \varepsilon, v_{\max} / n$, round each value down to a multiple of $K$, and run the dynamic program on the rounded values. The rounded optimum is at least $(1 - \varepsilon)$ times the true optimum, because the total rounding loss across at most $n$ items is at most $nK = \varepsilon v_{\max}$, and the true optimum is at least $v_{\max}$. The table now has $n v_{\max}/K = n^2/\varepsilon$ columns, so the running time is $O(n^3/\varepsilon)$.

The result is a fully polynomial-time approximation scheme: for any fixed $\varepsilon > 0$, a solution within a factor of $1 - \varepsilon$ is computed in time polynomial in both $n$ and $1/\varepsilon$. The cost is that the exponent on $n$ is 3 and the dependence on $1/\varepsilon$ is inverse-linear, so tightening the guarantee from 1% to 0.1% multiplies the work by ten. There is no scheme whose running time is polynomial in $\log(1/\varepsilon)$, since that would decide the problem exactly.

Why the same relaxation helps elsewhere and not universally

The pattern generalizes: relax integrality, solve the relaxation, and either round the solution or use its value as a bound. What differs between problems is how much the rounding costs.

For vertex cover, rounding the fractional solution at threshold $1/2$ gives a 2-approximation, and the analysis is a factor of 2 for the same reason as knapsack: each chosen vertex’s fractional value is at least $1/2$, and the fractional optimum is a lower bound. For set cover, the relaxation has an integrality gap of $\Theta(\log n)$: there are instances where the fractional optimum is 1 and every integral cover costs $\Omega(\log n)$. A rounding scheme that reads only the fractional value therefore cannot give a constant factor, which is why the greedy set cover bound is logarithmic rather than constant, and why the primal-dual construction must charge against dual variables rather than round primal ones.

For metric TSP, the relaxation that matters is not a linear program over the variables but a combinatorial bound: any tour contains a spanning tree, which is why the Christofides construction can start from a minimum spanning tree and repair it. The bound is structural, and the ratio is $3/2$ rather than 2.

The knapsack case is the cleanest because the relaxation’s vertices are so simple. One constraint, one split item, and the entire gap analysis reduces to comparing the split item’s value against the value already accumulated. Problems with many constraints have vertices with many fractional coordinates, and the analysis of the rounding error becomes correspondingly harder; that progression, from one constraint to many, is the progression from this problem to the covering problems above.