Difficulty: Intermediate to Advanced | Prerequisites: NP-completeness basics, polynomial-time reductions, Big-O notation
Approximation algorithms give guaranteed near-optimal solutions to NP-Hard problems in polynomial time. Load balancing analyses show how greedy heuristics perform relative to the optimum. Verifier construction for recipe-style problems and counting problems like #SAT round out the algorithmic toolkit tested in EECS 376.
Approximation algorithm
A polynomial-time algorithm that produces a solution within a guaranteed factor of the optimal solution for an NP-Hard optimisation problem. Think of it as: we cannot solve it perfectly in polynomial time, so we settle for "close enough" with a provable bound.
Approximation ratio (α)
For a maximisation problem, α = ALG / OPT, where 0 < α ≤ 1. An α-approximation algorithm guarantees ALG ≥ α · OPT. For minimisation, α = ALG / OPT ≥ 1, and we want α as close to 1 as possible.
OPT
The value of an optimal solution. We often do not know OPT exactly, so we bound it using structural arguments.
Makespan
In load balancing, the makespan is the maximum total load assigned to any single machine. The goal is to minimise the makespan.
#SAT (Sharp-SAT)
The problem of counting the number of satisfying assignments for a Boolean formula. The decision version asks whether a formula has at least k satisfying assignments.
L_Recipe
A decision problem about selecting m ingredients from n options to create a dish whose total discord penalty is at most p. Used as an example of NP verification via verifier construction.
Suppose A is a 2/3-approximation algorithm for the MaxClique problem, and let G = (V, E) be an undirected, unweighted input graph.
What this means: A(G) outputs a clique that has at least two-thirds as many vertices as a largest clique in G.
Let OPT denote the size of a maximum clique in G. Let ALG denote the size of the clique output by A(G). By hypothesis, ALG ≥ (2/3) · OPT.
Analysing the true statements:
"A(G) must output a clique in G of size at least 2|V|/3." This is false. It could be that ALG = (2/3) · OPT and OPT < |V|, so ALG < (2/3)|V|.
"A(G) must output a clique that has at least half as many vertices as a largest clique in G." This is true, since ALG ≥ (2/3) · OPT > (1/2) · OPT.
"A(G) must output a clique that has at least two-thirds as many vertices as a largest clique in G." This is true, by the definition of a 2/3-approximation.
"A(G) cannot output a largest clique in G." This is false. It could output the optimal clique.
"A(G) must output a larger clique than A'(G) does, where A' is a 1/2-approximation algorithm for MaxClique." This is false. Let ALG' denote the size of A'(G)'s output. We cannot conclude anything by comparing ALG and ALG'; we compare solely to OPT. Either one might be larger.
Key insight for approximation ratio questions: the guarantee is always relative to OPT, never relative to |V| or to another algorithm's output. A c-approximation says ALG ≥ c · OPT for maximisation (or ALG ≤ c · OPT for minimisation).
A load balancer assigns several tasks to worker machines without overloading any machine. Let Tᵢ ∈ [0, 4] be the amount of work the i-th task requires. No machine should get more than 4 units of work total. The goal is to minimise the number of machines.
The AssignTasks algorithm (greedy):
For i = 1 to k do:
If task i can be assigned to some already-provisioned machine (without overloading it), assign task i to such a machine
Else provision a new machine and assign task i to it
Return the assignment
Part (a): AssignTasks provisions M machines such that Σ Tᵢ > 2(M - 1)
At most one provisioned machine can end up having ≤ 2 units of work. Suppose two machines both had ≤ 2. Then the first one would have been able to take on every task the other one was assigned, so the algorithm would never have provisioned that other one. Since at least M - 1 of the machines have > 2 units of work, the total Σ Tᵢ > 2(M - 1).
Part (b): M < 2 · OPT + 1, so M ≤ 2 · OPT
Let M be the number of machines provisioned by AssignTasks. Lower bound OPT in terms of Σ Tᵢ: since OPT ≥ Σ Tᵢ / 4 (equivalently, 4 · OPT ≥ Σ Tᵢ), and no machine can be assigned more than 4 units of work, we need at least Σ Tᵢ / 4 machines.
From part (a): Σ Tᵢ > 2(M - 1), so combining: 4 · OPT > 2(M - 1). Simplifying: M < 2 · OPT + 1. Since M and OPT are integers, M ≤ 2 · OPT.
This makes AssignTasks a 2-approximation algorithm for the machine minimisation problem.
There are n ingredients to work with, and we wish to use m of them (m ≤ n) to create a new dish. An n × n matrix D[i, j] indicates the discord between ingredients i and j, where 0 means they go together perfectly and 10 means they go together very badly. The penalty of a dish is the sum of the discord between each pair of ingredients.
L_Recipe = { (D, n, m, p) : there is a dish with ≥ m ingredients that has penalty ≤ p }
Showing L_Recipe ∈ NP
The certificate is a list of the ingredients proposed: S = (s₁, s₂, ..., sₘ).
Verifier V((D, m, p), S):
P := 0
If |S| < m then reject
For k = 1 to k = n do:
For l = k + 1 to l = n do:
P = P + D[sₖ][sₗ]
If P > p then reject
Accept
Correctness of the verifier:
If (S, n, m, p, D) ∈ L_Recipe, then |S| ≥ m and the total penalty is ≤ p. So the verifier accepts.
If the verifier accepts, then the certificate has at least m ingredients and total penalty ≤ p. So (S, n, m, p, D) ∈ L_Recipe.
To avoid double-counting penalties, the verifier only considers the lower triangle of the matrix D (the nested loop with l > k).
Runtime analysis:
The first if statement checks the number of ingredients, taking O(m) time
The double for loop runs O(|S|²) = O(n²) pairs
The time complexity is polynomial with respect to the input size
Definition: #SAT is the problem of determining how many satisfying assignments a Boolean formula φ has.
The decision version: L_#SAT = { (φ, k) : φ is a Boolean formula with ≥ k satisfying assignments }
Can an efficient decider for L_#SAT efficiently solve #SAT?
Suppose we have an efficient decider D for L_#SAT. The following algorithm would efficiently solve #SAT:
On input φ:
k ← 0
While D(φ, k + 1) accepts:
k ← k + 1
Return k²
The answer is False. A Boolean formula over n variables can have up to 2ⁿ satisfying assignments. If each variable appears a constant number of times in φ, then φ has length O(n). However, A(φ) can do 2ⁿ iterations of the loop, for a runtime of Ω(2ⁿ). This is not polynomial with respect to the input size.
Concrete example: (x₁ ∨ ¬x₁) ∧ (x₂ ∨ ¬x₂) ∧ ... ∧ (xₙ ∨ ¬xₙ). This formula has size 2n and 2ⁿ satisfying assignments, so the loop runs exponentially many times.
The key issue is that the number of satisfying assignments can be exponential in the input size, so iterating through them one at a time is not polynomial.
Students often confuse the approximation ratio direction. For maximisation, a 2/3-approximation means ALG ≥ (2/3) · OPT (the algorithm gets at least 2/3 of optimal). For minimisation, a 2-approximation means ALG ≤ 2 · OPT.
The approximation guarantee is always relative to OPT, not relative to the input size |V| or another algorithm's output. Two different approximation algorithms cannot be compared directly by their ratios alone on a given instance.
Having an efficient decider for a counting problem's decision version does not automatically give an efficient counting algorithm. The number of solutions can be exponential, and iterating through them one at a time is not polynomial.
In the AssignTasks analysis, the bound M ≤ 2 · OPT comes from integrality (both M and OPT are integers), not directly from the inequality M < 2 · OPT + 1. Missing this step loses the tight bound.
⚠️ Approximation ratio questions often present several statements about an algorithm's output and ask you to select all true ones. Read each carefully against the formal definition ALG ≥ α · OPT.
⚠️ Load balancing proofs follow a pattern: show a structural property of the greedy algorithm (part a), then use it to bound M relative to OPT (part b). Both parts are commonly tested.
⚠️ Verifier construction for novel problems (like L_Recipe) is a staple. You must give the certificate, the verifier pseudocode, correctness in both directions, and the runtime analysis.
⚠️ The #SAT question tests whether you recognise that polynomial-time decidability of a decision version does not imply polynomial-time solvability of the corresponding counting or search problem.
True or False: A 2/3-approximation for a maximisation problem guarantees the output is at least 2/3 of the input size. (False, it is 2/3 of OPT)
True or False: AssignTasks is a 2-approximation for machine minimisation. (True)
Fill in the blank: In the AssignTasks analysis, at most ______ machine(s) can end up with ≤ 2 units of work. (One)
True or False: An efficient decider for L_#SAT gives an efficient algorithm for counting all satisfying assignments. (False)
True or False: The certificate for L_Recipe is the list of selected ingredients. (True)
Q: A is a 2/3-approximation algorithm for MaxClique. Must A(G) output a clique of size at least 2|V|/3?
A: No. The guarantee is ALG ≥ (2/3) · OPT, and OPT can be much smaller than |V|. So ALG can be much smaller than 2|V|/3.
Q: In the AssignTasks problem, why is M < 2 · OPT + 1 rather than M ≤ 2 · OPT?
A: From part (a), Σ Tᵢ > 2(M - 1). Combined with 4 · OPT ≥ Σ Tᵢ, we get 4 · OPT > 2(M - 1), which gives M < 2 · OPT + 1. Since M and OPT are integers, this rounds down to M ≤ 2 · OPT.
Q: Why does the naive algorithm for #SAT (incrementing k while D(φ, k+1) accepts) fail to run in polynomial time?
A: The number of satisfying assignments can be as large as 2ⁿ, so the while loop can iterate up to 2ⁿ times. This is exponential in the input length, not polynomial.
Q: In the L_Recipe verifier, why do we only consider pairs (k, l) with l > k?
A: To avoid double-counting the discord. D[i, j] and D[j, i] represent the same pair, so we traverse only the lower triangle of the matrix.
Approximation algorithm, approximation ratio, MaxClique, maximum clique, clique problem, load balancing, makespan, greedy algorithm, AssignTasks, machine minimisation, NP verification, verifier construction, recipe problem, discord matrix, #SAT, sharp-SAT, counting satisfying assignments, Boolean formula, decision problem vs counting problem, EECS 376, foundations of computer science, University of Michigan