Chapter 14. Approximation Algorithms

Lattice-linear approximations: lex-first vertex cover, lex-first set cover, and an FPTAS for knapsack on the scaled-value lattice.

This page: LLP forms. View classical forms »

From hardness to approximation

Chapter 13 established that Vertex Cover, Set Cover, and Knapsack are NP-hard. An $\alpha$-approximation algorithm trades optimality for polynomial time: on every instance it returns a feasible solution whose cost is within a factor $\alpha$ of the optimum (or, for maximization, at least $1/\alpha$ of the optimum). The classical companion page lists three such algorithms in their textbook “greedy / DP” form. This page recasts each of them as a lattice-linear program: an initial state $G$, a forbidden predicate, and an advance rule that monotonically grows $G$ until no index is forbidden.

Why an LLP form?

The classical 2-approximation for vertex cover picks edges one at a time — each iteration depends on the result of the previous one. The LLP recasting breaks that serial dependency: we declare a vertex $j$ forbidden exactly when some uncovered edge incident to $j$ is the lexicographically smallest uncovered edge in the entire graph; advancing sets $G[j] := \mathrm{true}$. Multiple lex-first edges can fire concurrently, and the final set $C$ (once no edge remains forbidden) is exactly the set produced by the classical algorithm. The same recipe works for the greedy $H_n$-approximation for Set Cover (forbidden = lex-tied maximum coverage) and for the FPTAS for Knapsack (forbidden = the DP relaxation $G[i,c]$ is below the take-or-skip target).

LLP-LexMatchVertexCover

A parallel $2$-approximation. The state vector $G \in \{0, 1\}^{|V|}$ marks which vertices are in the cover. Vertex $j$ is forbidden when there exists some $i$ such that the edge $(i, j)$ is the lex-minimum uncovered edge. Advancing fires every endpoint of every lex-minimal uncovered edge in parallel; once no edge remains forbidden, $G$ is a vertex cover whose size is at most twice the optimum.

Time complexity: $O(|V|^2 \cdot |E|)$ in the unoptimized form below; the classical variant runs in $O(|V| + |E|)$.

LLP-LexGreedySetCover

A parallel $H_n$-approximation. Given $m$ subsets of an $n$-element universe, $G[j] \in \{0, 1\}$ marks which subsets are picked. Set $j$ is forbidden if it currently covers at least one uncovered element and no still-unpicked neighbor covers strictly more, with ties broken by smaller index. Advancing fires every lex-tied maximum-coverage set in parallel.

Time complexity: $O(m^2 \cdot n)$ per round; no set remains forbidden after $O(m)$ rounds.

LLP-ApproxKnapsack

An FPTAS for $0/1$ Knapsack. Given items with integer weights $w_i$ and values $v_i$, capacity $W$, and a precision $\epsilon = \mathrm{epsNum}/\mathrm{epsDen}$, discard items that cannot fit and scale the survivors' values into $v'_i = \lfloor v_i \cdot n_f \cdot \mathrm{epsDen} / (\mathrm{epsNum} \cdot M) \rfloor$ where $n_f$ is the number of feasible items and $M = \max_i v_i$ among them. The state is a profit-indexed table $D[i, p]$ — the minimum weight of a subset of the first $i$ items reaching scaled profit at least $p$ — not a capacity-indexed one: a capacity-indexed table would grow with $W$ and remain only pseudo-polynomial. The forbidden/advance loop relaxes each cell to the better of “skip item $i$” and “take item $i$”; the answer is $p^* = \max\{p : D[n_f, p] \le W\}$, whose unscaled profit is guaranteed to be within a $(1 - \epsilon)$ factor of the optimum.

Time complexity: $O(n^3 / \epsilon)$, independent of $W$; the table is of size $(n_f + 1) \times (V' + 1)$ where $V' = O(n_f^2/\epsilon)$.

LLP-Weighted-Vertex-Cover

Primal-dual 2-approximation for weighted vertex cover: an edge $\{u,v\}$ is forbidden (slack) when neither endpoint is tight and it is the lexicographically smallest such edge sharing a vertex with any other slack edge; the advance raises its price by the smaller of its two endpoints' remaining budgets. Distinct lex-minimal slack edges are pairwise non-adjacent, so they may advance independently in the same round — the fixpoint scan below realizes exactly this forbidden/advance predicate.

LLP-Weighted-Set-Cover

Primal-dual $f$-approximation for weighted set cover: element $x$ is forbidden (slack, lies in no tight set) when it is also the lexicographically smallest such element sharing a set with any other slack element; the advance raises its price by the smallest remaining budget among the sets containing it. Distinct lex-minimal slack elements never share a set, so they may advance independently in the same round — the fixpoint scan below realizes exactly this forbidden/advance predicate.

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[j]$ represents and the negation of the forbidden clause from the matching .llp source.

Looking ahead

The LLP recasting of approximation algorithms makes the parallelism explicit and the correctness invariant readable. The classical forms — including the matching-based vertex cover, the greedy $H_n$-approximation for set cover, and the FPTAS for knapsack with its backtracking step — are on the classical companion page. For the exact (NP-hard) versions of the same problems, see Chapter 13. Intractability.