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 sequentially — 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 fixed point is exactly the set $C$ 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-LexicallyFirstVertexCover
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; the fixed point is a vertex cover whose size is at most twice the optimum.
Time complexity: $O(|V|^2 \cdot |E|)$ in the unoptimised form below; the classical sequential variant runs in $O(|V| + |E|)$.
boolean[] LLPLexicallyFirstVertexCover(int[][] adj) {
boolean[] G = false;
forbidden (j) :
exists i in [0..n-1] : isLexMinIncident(i, j, adj, G)
=>
advance : G[j] = true;
return G;
}
LLP-LexicallyFirstSetCover
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 neighbour 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; the fixed point is reached in $O(m)$ rounds.
boolean[] LLPLexicallyFirstSetCover(int[][] S) {
boolean[] G = false;
forbidden (j) : isLexMaxCov(j, S, G) =>
advance : G[j] = true;
return G;
}
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}$, scale the values into $v'_i = \lfloor v_i \cdot n \cdot \mathrm{epsDen} / (\mathrm{epsNum} \cdot M) \rfloor$ where $M = \max_i v_i$. The state is the standard $2\text{D}$ DP table $G[i, c]$. The forbidden / advance loop relaxes each cell to the better of “skip item $i$” and “take item $i$”; the fixed point is guaranteed to be within a $(1 - \epsilon)$ factor of the optimal value.
Time complexity: $O(n^2 \cdot W \cdot \mathrm{epsDen} / \mathrm{epsNum})$ in the worst case; the table itself is of size $(n + 1) \times (W + 1)$.
int[][] LLPApproxKnapsack(int[] w, int[] v, int W,
int epsNum, int epsDen) {
int n = w.length;
int M = max(v);
int[] vPrime = new int[n];
for (int i = 0; i < n; i++)
vPrime[i] = (v[i] * n * epsDen) / (epsNum * M);
int[][] G = new int[n + 1][W + 1];
forbidden (i, c) :
G[i][c] < max(G[i-1][c],
(w[i-1] <= c ? G[i-1][c-w[i-1]] + vPrime[i-1] : 0))
=>
advance : G[i][c] = max(...);
return G;
}
LLP-Weighted-Vertex-Cover
Primal-dual 2-approximation for weighted vertex cover: an edge $\{u,v\}$ is forbidden (slack) when neither endpoint is tight; the advance raises prices uniformly.
// LLP-WeightedVertexCover: primal-dual 2-approximation for weighted vertex cover.
// Edges are indexed by pairs; G[e] is the price on edge e.
// forbidden: edge {u,v} is slack (neither endpoint tight).
// advance: raise G[e] by the uniform step r.
class LLPWeightedVertexCover {
void LLPWeightedVertexCover(int[][] adj, double[] w) {
int nv = w.length;
double[][] G = new double[nv][nv];
boolean changed = true;
while (changed) {
changed = false;
double r = computeStep(adj, w, G, nv);
if (r <= 0.0) { changed = false; };
int u = 0;
while (u < nv) {
int v = u + 1;
while (v < nv) {
if (adj[u][v] == 1 && !tight(u, adj, w, G, nv) && !tight(v, adj, w, G, nv)) {
G[u][v] = G[u][v] + r;
G[v][u] = G[v][u] + r;
changed = true;
};
v = v + 1;
};
u = u + 1;
}
};
}
boolean tight(int v, int[][] adj, double[] w, double[][] G, int nv) {
double sum = 0.0;
int u = 0;
while (u < nv) {
if (adj[u][v] == 1) { sum = sum + G[u][v]; };
u = u + 1;
};
return sum >= w[v];
}
double computeStep(int[][] adj, double[] w, double[][] G, int nv) {
double r = infinity;
int v = 0;
while (v < nv) {
int slackDeg = 0;
int u = 0;
while (u < nv) {
if (adj[u][v] == 1 && !tight(u, adj, w, G, nv) && !tight(v, adj, w, G, nv)) {
slackDeg = slackDeg + 1;
};
u = u + 1;
};
if (slackDeg > 0) {
double sum = 0.0;
u = 0;
while (u < nv) {
if (adj[u][v] == 1) { sum = sum + G[u][v]; };
u = u + 1;
};
double ratio = (w[v] - sum) / slackDeg;
if (ratio < r) { r = ratio; };
};
v = v + 1;
};
return r;
}
}
LLP-Weighted-Set-Cover
Primal-dual $f$-approximation for weighted set cover: element $e$ is forbidden (slack) when it lies in no tight set; the advance raises its price.
// LLP-WeightedSetCover: primal-dual f-approximation for weighted set cover.
// G[e] is the price on element e. A set s is tight when sum of prices >= w[s].
// forbidden: element e is slack (lies in no tight set).
// advance: raise G[e] by uniform step r.
// Note: this algorithm appears under \remove{} in the book.
class LLPWeightedSetCover {
void LLPWeightedSetCover(int[][] S, double[] w) {
int m = w.length;
int u = S[0].length;
double[] G = new double[u];
boolean changed = true;
while (changed) {
changed = false;
double r = computeStep(S, w, G, m, u);
if (r <= 0.0) { changed = false; };
int e = 0;
while (e < u) {
if (isSlack(e, S, w, G, m)) {
G[e] = G[e] + r;
changed = true;
};
e = e + 1;
}
};
}
boolean setTight(int s, int[][] S, double[] w, double[] G) {
double sum = 0.0;
int e = 0;
while (e < G.length) {
if (S[s][e] == 1) { sum = sum + G[e]; };
e = e + 1;
};
return sum >= w[s];
}
boolean isSlack(int e, int[][] S, double[] w, double[] G, int m) {
int s = 0;
while (s < m) {
if (S[s][e] == 1 && setTight(s, S, w, G)) { return false; };
s = s + 1;
};
return true;
}
double computeStep(int[][] S, double[] w, double[] G, int m, int u) {
double r = infinity;
int s = 0;
while (s < m) {
int slackCount = 0;
int e = 0;
while (e < u) {
if (S[s][e] == 1 && isSlack(e, S, w, G, m)) {
slackCount = slackCount + 1;
};
e = e + 1;
};
if (slackCount > 0) {
double sum = 0.0;
e = 0;
while (e < u) {
if (S[s][e] == 1) { sum = sum + G[e]; };
e = e + 1;
};
double ratio = (w[s] - sum) / slackCount;
if (ratio < r) { r = ratio; };
};
s = s + 1;
};
return r;
}
}
VertexImplications
Implication closure for vertex cover: $w$ is forbidden when some vertex $v$ with $(v,w)$ an implication edge is in the cover but $w$ is not; the advance adds $w$.
// VertexImplications: if v is in the cover and (v,w) is an implication,
// then w must also be in the cover.
// forbidden(w): exists v with (v,w) in I and G[v]=1 and G[w]=0.
// advance: G[w] := 1.
class VertexImplications {
void VertexImplications(int[][] I, boolean[] G) {
forbidden (w) :
exists v in [0..n-1] : I[v][w] == 1 && G[v] && !G[w]
=>
advance : G[w] = true;
}
}
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.
| Algorithm | $G[j]$ | Negation of the forbidden clause |
|---|---|---|
| LLP-LexicallyFirstVertexCover | $G[j] \in \{0,1\}$ — is vertex $j$ in the cover? | $\forall j,\, \forall i \in [0..n-1]:\ \neg\,\mathrm{isLexMinIncident}(i, j, \mathrm{adj}, G)$ |
| LLP-LexicallyFirstSetCover | $G[j] \in \{0,1\}$ — is set $j$ picked? | $\forall j:\ \neg\,\mathrm{isLexMaxCov}(j, S, G)$ |
| LLP-ApproxKnapsack | $G[i, c]$ — best scaled value using items $\leq i$ with capacity $c$ | $\forall i, c:\ G[i, c] \geq \max\bigl(G[i-1, c],\ \mathbb{1}[w_{i-1} \leq c] \cdot (G[i-1, c - w_{i-1}] + v'_{i-1})\bigr)$ |
Looking ahead
The LLP recasting of approximation algorithms makes the parallelism explicit and the correctness invariant readable. The classical sequential 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.