Difficulty: Intermediate to Advanced | Prerequisites: NP-Completeness, BIN-PACKING, Knapsack problem, HAM-CYCLE, TSP basics.
Since NP-Complete problems (likely) have no efficient exact algorithms, approximation algorithms are the practical alternative. These are polynomial-time algorithms that produce solutions guaranteed to be within some factor of optimal. This material covers three key results: first-fit greedy gives a 2-approximation for BIN-PACKING, Smart-Greedy gives a 1/2-approximation for 0-1 Knapsack, and no polynomial-time approximation algorithm exists for general TSP unless P = NP. The last result is striking because it means general TSP is "inapproximable" (whereas Euclidean TSP does admit approximation).
First-fit greedy never uses more than twice the optimal number of bins because no two bins can both be less than half full. Smart-Greedy for Knapsack takes the better of a value-density-sorted greedy and the single most valuable item, achieving at least half the optimal fractional value. For general TSP, any α-approximation algorithm could distinguish Hamiltonian from non-Hamiltonian graphs, which would put HAM-CYCLE in P and imply P = NP.
α-approximation algorithm
A polynomial-time algorithm whose output is guaranteed to be within a factor α of the optimal solution. For maximisation problems, the output is at least (1/α) times the optimal. For minimisation problems, the output is at most α times the optimal. In simple terms, it is a fast algorithm that might not give the best answer but guarantees the answer is not too far off.
First-fit greedy (for BIN-PACKING)
A greedy algorithm that processes items one by one, placing each in the first existing bin with enough space, or opening a new bin if none fits.
Fractional knapsack
A variant of the knapsack problem where you may take any fraction t ∈ [0, 1] of an item, adding t × value and t × weight. The optimal fractional solution is always at least as good as the optimal 0-1 solution because every 0-1 choice is also a valid fractional choice.
Relatively-Greedy algorithm
Sorts items by value-to-weight ratio (value density) in decreasing order, then greedily takes items that fit. Produces a solution that may miss the optimal by the value of one item.
Dumb-Greedy algorithm
Simply takes the single item with the highest value that fits in the knapsack.
Smart-Greedy algorithm
Runs both Relatively-Greedy and Dumb-Greedy, then returns whichever produces the higher total value. This achieves a 1/2-approximation for the 0-1 knapsack problem.
Hamiltonian cycle (HAM-CYCLE)
A cycle in a graph that visits every vertex exactly once and returns to the starting vertex. Deciding whether a graph has a Hamiltonian cycle is NP-Complete.
Travelling Salesman Problem (TSP)
Find the minimum-weight tour visiting all vertices exactly once in a complete weighted graph. The general version has no known polynomial-time approximation algorithm (unless P = NP).
The algorithm (Greedo's algorithm):
On input ⟨v, A⟩:
Initialise the set of used bins S = ∅.
For each item i ∈ {1, ..., n}: iterate over S and place item i in the first bin with enough remaining space.
If no bin fits, open a new bin and place the item there.
Return S and b = |S|.
Proving b ≤ 2b (where b is the optimal number of bins):**
Step 1, lower bound on b*: In the best case, every bin is filled to capacity v. So b* ≥ (Σ A[i]) / v.
Step 2, upper bound on b: No two bins can both be less than half full. Suppose bins s₁ and s₂ both have total weight ≤ v/2. Then all items in s₂ could have fit in s₁ (since s₁ has at least v/2 space remaining). But the algorithm places items in the first available bin, so it would have placed s₂'s items in s₁ rather than opening s₂. Contradiction.
Since at most one bin is less than half full, pairing consecutive bins gives:
2 × Σ A[i] = 2 × Σ wᵢ = (w₁ + w₂) + (w₂ + w₃) + ... + (wᵦ + w₁) > b × v
This gives b/2 ≤ (Σ A[i]) / v.
Combining: b* ≥ (Σ A[i]) / v ≥ b/2, so b ≤ 2b*.
Edge cases:
b* = 0 (no items or all items exceed bin capacity): Greedo also returns b = 0.
b* = 1: all items fit in one bin, so Greedo places everything in the first bin. b = 1 = b*. Both satisfy b ≤ 2b*.
This proof proceeds in three parts.
Every valid choice in the 0-1 knapsack (take item entirely or leave it) is also a valid choice in the fractional knapsack (just set t = 1 or t = 0). So the fractional problem's feasible set is a superset of the 0-1 problem's feasible set. The optimal fractional value S* is therefore at least as large as the optimal 0-1 value.
Let S₁* be the value returned by Relatively-Greedy and S₂* be the value returned by Dumb-Greedy.
The optimal fractional solution is obtained by a modified Relatively-Greedy: sort by value/weight ratio, take items greedily, and when the next item does not fit whole, take whatever fraction fills the knapsack.
So S* = S₁* + F, where F is the fractional value of that last partially-taken item.
F is at most the full value of the single most valuable item (because a fraction of an item is worth less than or equal to the whole item). The single most valuable item is exactly what Dumb-Greedy takes, so F ≤ S₂*.
Therefore S* = S₁* + F ≤ S₁* + S₂*.
Smart-Greedy returns max{S₁*, S₂*}.
max{S₁*, S₂*} ≥ (S₁* + S₂*) / 2 ≥ S* / 2 (by part b) ≥ OPT₀₋₁ / 2 (by part a).
So Smart-Greedy is a 1/2-approximation for 0-1 Knapsack.
This is an inapproximability result: for any α > 1, an efficient α-approximation for general TSP would imply P = NP.
The reduction from HAM-CYCLE:
Given graph G = (V, E), construct a complete weighted graph f(G) = (V', E'):
V' = V (same vertices).
For each edge e ∈ E': w(e) = 1 if e ∈ E (original edge), w(e) = 2αn if e ∉ E (new edge), where n = |V|.
Analysis:
If G has a Hamiltonian cycle: f(G) has a tour T with w(T) = n (all n edges have weight 1). An α-approximation algorithm A returns a tour T' with w(T') ≤ αn.
If G does not have a Hamiltonian cycle: any tour in f(G) must use at least one edge not in E, which has weight 2αn. So every tour T has w(T) ≥ 2αn. The approximation algorithm returns w(T') ≥ 2αn.
The gap:
When G ∈ HAM-CYCLE: w(T') ≤ αn. When G ∉ HAM-CYCLE: w(T') ≥ 2αn.
Since αn < 2αn, the output of A on f(G) tells you definitively whether G has a Hamiltonian cycle. Since f is polynomial-time computable and A is efficient, this would place HAM-CYCLE in P, which would mean P = NP (since HAM-CYCLE is NP-Complete).
BIN-PACKING lower bound: b* ≥ (Σ A[i]) / v
BIN-PACKING upper bound (first-fit): b/2 ≤ (Σ A[i]) / v, giving b ≤ 2b*
Knapsack fractional decomposition: S* = S₁* + F, where F ≤ S₂*
Knapsack approximation: max{S₁*, S₂*} ≥ (S₁* + S₂*) / 2 ≥ S* / 2 ≥ OPT / 2
TSP gap construction weights: w(e) = 1 if e ∈ E, w(e) = 2αn if e ∉ E
BIN-PACKING approximations are used in cloud computing (packing virtual machines onto physical servers), logistics (container loading), and memory management. The Knapsack problem models resource allocation, investment portfolio selection, and cargo loading. TSP appears in delivery route optimisation, circuit board drilling, and genome sequencing.
Students often confuse the direction of the approximation ratio. For minimisation (BIN-PACKING), a 2-approximation means the output is at most 2× optimal. For maximisation (Knapsack), a 1/2-approximation means the output is at least 1/2 of optimal.
Students sometimes think the TSP inapproximability result applies to all versions of TSP. It applies to general (arbitrary weights) TSP only. Euclidean TSP (where distances satisfy the triangle inequality) does admit approximation algorithms.
In the BIN-PACKING proof, students sometimes miss that the pairing argument only works when b* ≥ 2. The edge cases b* = 0 and b* = 1 need separate (but simple) treatment.
For the Knapsack proof, students forget the assumption that every item's weight is at most the knapsack capacity. Without this, an item might be too heavy to take at all, breaking the Dumb-Greedy argument.
⚠️ The BIN-PACKING 2-approximation proof is a classic exam question. The key step is arguing that two bins cannot both be less than half full. Make sure you can reproduce the pairing/summing argument.
⚠️ For the Knapsack 1/2-approximation, understand the three-part structure: (a) fractional ≥ 0-1, (b) S₁* + S₂* ≥ S*, (c) max ≥ average ≥ half. Each part is short, but skipping one breaks the proof.
⚠️ The TSP inapproximability proof is a model for "gap-producing reductions." The idea of choosing edge weights to create a detectable gap between yes- and no-instances is a technique that appears beyond this course.
⚠️ Know the difference between Euclidean TSP (triangle inequality, approximation exists) and general TSP (no approximation unless P = NP).
True or False: First-fit greedy always produces the optimal number of bins. Answer: False. It produces at most 2× optimal.
Fill in the blank: Smart-Greedy returns max{S₁*, S₂*}, which is at least ______ of the optimal 0-1 knapsack value. Answer: 1/2.
True or False: An efficient 3-approximation for general TSP would imply P = NP. Answer: True. The inapproximability result holds for any α > 1.
Fill in the blank: In the TSP gap construction, edges not in the original graph are assigned weight ______. Answer: 2αn.
True or False: The fractional knapsack optimal is always strictly greater than the 0-1 optimal. Answer: False. It is at least as large, but can be equal (when the 0-1 optimal happens to fill the knapsack exactly).
Q: In the first-fit greedy BIN-PACKING proof, why can we not have two bins both filled to at most half capacity?
A: If bins s₁ and s₂ both have total weight ≤ v/2, then s₁ has at least v/2 remaining capacity, which is enough to hold all items in s₂. The first-fit algorithm would have placed s₂'s items in s₁ rather than creating s₂. This is a contradiction.
Q: Why does Smart-Greedy run both sub-algorithms rather than just Relatively-Greedy?
A: Relatively-Greedy alone can perform arbitrarily badly. Consider one very valuable but heavy item and many low-value light items. Relatively-Greedy might fill the knapsack with light items and miss the valuable one. Dumb-Greedy catches this case. Taking the maximum of both guarantees at least half the fractional optimum.
Q: In the TSP inapproximability proof, why is the weight of non-original edges set to 2αn rather than just a large constant?
A: It must be large enough that any tour using even one such edge has total weight strictly greater than αn (the upper bound when G has a Hamiltonian cycle). Since a tour has n edges and the α-approximation multiplies the optimal by α, the threshold αn must be exceeded. Setting the penalty to 2αn guarantees w(T') ≥ 2αn > αn, creating a clean gap.
Q: Explain why the fractional knapsack optimum is an upper bound on the 0-1 optimum.
A: Every feasible solution to the 0-1 problem is also feasible in the fractional problem (with t = 0 or t = 1 for each item). The fractional problem has strictly more feasible solutions (partial takes). So its optimum is at least as large.
The BIN-PACKING approximation connects to the NP-Completeness proof from Q3a (same problem, different angle: since we cannot solve it exactly in polynomial time, we approximate). This illustrates the broader theme: NP-Completeness motivates approximation.
The Knapsack approximation connects to dynamic programming approaches for Knapsack (pseudo-polynomial time) and to fully polynomial-time approximation schemes (FPTAS), which achieve (1 - ε)-approximation for any ε > 0.
The TSP inapproximability result contrasts with the 2-approximation for metric TSP (triangle inequality) and the 3/2-approximation of Christofides' algorithm for metric TSP, covered in Section Notes 8.
Related Terms / Search Tags
approximation algorithm, approximation ratio, first-fit greedy, bin packing approximation, knapsack approximation, Smart-Greedy, Relatively-Greedy, Dumb-Greedy, fractional knapsack, 0-1 knapsack, TSP inapproximability, Hamiltonian cycle, travelling salesman problem, gap reduction, EECS 376, computational complexity, NP-Hard approximation