1 Why Approximation Algorithms?
Key Terminology: Polynomial Time and NP-Hardness
Polynomial time: An algorithm runs in
polynomial time if its running time is bounded by a polynomial function of the input size n — such as O(n), O(n²), or O(n³). These algorithms are considered
efficient and practical even for large inputs.
NP-hard: A problem is
NP-hard if it is at least as hard as the hardest problems in the class
NP (Nondeterministic Polynomial time — problems whose solutions can be
verified quickly, even if
finding a solution is hard). No one has ever found a polynomial-time algorithm for any NP-hard problem, and most computer scientists believe none exists. If someone did find one, it would prove
P = NP — one of the greatest unsolved problems in mathematics and computer science.
Many important optimization problems are NP-hard — no known polynomial-time algorithm can solve them exactly. Examples include:
Classic NP-Hard Problems at a Glance
Vertex Cover: Find the smallest set of vertices that touches every edge in a graph.
Traveling Salesman Problem (TSP): Find the shortest route visiting every city exactly once and returning to the start (defined in detail below).
Set Cover: Cover all elements using the fewest sets from a given collection.
Graph Coloring: Assign colors to vertices so that no two adjacent vertices share the same color, using the fewest colors possible.
Knapsack: Given items with weights and values, pack the most valuable combination into a bag without exceeding its weight capacity.
Scheduling: Assign jobs to machines to minimize the total completion time.
What is the Traveling Salesman Problem (TSP)?
Given a set of
n cities and the
distances between every pair of cities, the goal is to find the
shortest possible route that visits each city
exactly once and returns to the starting city. In other words, find the minimum-cost
Hamiltonian cycle (a cycle that passes through every vertex exactly once) in a complete weighted graph. TSP is one of the most famous NP-hard problems — easy to state, but no known algorithm solves it efficiently for all inputs.
We have three options when facing an NP-hard problem:
Three Strategies for NP-Hard Problems
1. Exact algorithms — solve it perfectly, but with exponential time. OK for small inputs only.
2. Heuristics — fast, often work well in practice, but
no worst-case guarantee.
3. Approximation algorithms — polynomial time AND
provably close to optimal. The best of both worlds!
This lecture focuses on option 3: algorithms that are fast AND come with mathematical guarantees on solution quality.
Same Problem, Different Answer — Why "Approximation"?
It is important to understand: the
problem does not change. Vertex Cover still asks for the
smallest cover. TSP still asks for the
shortest tour. Set Cover still asks for the
fewest sets. These are the original optimization problems.
What changes is
what we are willing to accept as an answer:
Exact algorithm (the "correct" solution): Finds the absolute best answer — the true optimum. For example, the smallest possible vertex cover of size 5. But it may take exponential time (e.g., checking all 2ⁿ subsets), so for large inputs it is completely impractical.
Approximation algorithm: Finds a
valid answer that is
close to the optimum, with a
mathematical guarantee on how close. For example, a vertex cover of size 9 when the optimum is 5 — not perfect, but guaranteed to be at most 2× the optimum, and found in milliseconds instead of years.
We call them "approximations" because the
solution is approximate, not the problem. The cover returned is still a real, valid vertex cover — every edge is covered. The tour returned is still a real, valid tour — every city is visited. They are
correct solutions, just
not the optimal ones. The word "approximation" refers to the
quality (how close to optimal), not the
validity (the answer always works).
A Common Misconception
Approximation algorithms do
not produce "wrong" or "broken" answers. A 2-approximation vertex cover is a
perfectly valid cover — it just might use more vertices than strictly necessary. Think of it this way:
•
Exact solution: "Here is the cheapest flight route: $500." (took 3 days to compute)
•
Approximation: "Here is a flight route for $900. I guarantee it costs at most 2× the cheapest possible." (computed instantly)
Both routes get you to your destination. The approximation just might cost more — but you
know how much more, and you get the answer
now.
Real-World Applications
Network design: Finding minimum-cost networks that connect all nodes (related to TSP and the
Steiner tree problem — finding the shortest tree that connects a given subset of vertices, possibly using additional intermediate vertices).
Resource allocation: Covering all requirements with fewest resources (Set Cover).
Security: Placing minimum sensors to monitor all connections (Vertex Cover).
Logistics: Route planning for delivery trucks (TSP variants).
Cloud computing: Scheduling jobs on machines to minimize
makespan (the total time from when the first job starts until the last job finishes — i.e., the length of the overall schedule).
2 Approximation Ratio
Before defining the approximation ratio, we need to understand the two types of optimization problems:
Minimization vs. Maximization Problems
Minimization problem: The goal is to
make the cost as small as possible. The optimal solution has the
lowest cost. Examples: Vertex Cover (fewest vertices), TSP (shortest tour), Set Cover (fewest sets).
In a minimization problem, our algorithm's solution
C is always
≥ C* (we can never do better than optimal), so the ratio
C / C* is always ≥ 1.
Maximization problem: The goal is to
make the value as large as possible. The optimal solution has the
highest value. Examples: MAX-SAT (satisfy the most clauses), Maximum Independent Set (largest set of non-adjacent vertices), Maximum Cut (largest cut in a graph).
In a maximization problem, our algorithm's solution
C is always
≤ C* (we can never exceed optimal), so the ratio
C* / C is always ≥ 1.
An algorithm has approximation ratio ρ(n) if for every input of size n:
For minimization: C / C* ≤ ρ(n) (our solution is at most ρ times the optimal cost)
For maximization: C* / C ≤ ρ(n) (optimal is at most ρ times our solution's value)
where C = algorithm's solution cost/value
C* = optimal solution cost/value
A ρ-approximation algorithm always produces a solution within factor ρ of the best possible. The closer ρ is to 1, the better. Note that ρ(n) ≥ 1 for both types — a ratio of 1 means the algorithm always finds the exact optimum.
Approximation Ratio Examples
Minimization example (Vertex Cover): If the optimal cover has 5 vertices and our algorithm returns 9 vertices, the ratio is 9/5 = 1.8. A 2-approximation guarantees this ratio will never exceed 2.
Maximization example (MAX-SAT): If the optimal assignment satisfies 100 clauses and our algorithm satisfies 75, the ratio is 100/75 ≈ 1.33. A 4/3-approximation guarantees this ratio will never exceed 4/3.
What Does "2-Approximation" Mean?
A
2-approximation algorithm is an algorithm with approximation ratio
ρ = 2. Concretely:
For a minimization problem: the algorithm's solution is guaranteed to cost
at most 2 times the optimal cost. If the best possible answer is 10, our algorithm will return a solution costing at most 20 — never worse.
For a maximization problem: the algorithm's solution is guaranteed to have value
at least half of the optimal value. If the best possible value is 100, our algorithm will return at least 50 — never less.
More generally, a
k-approximation algorithm guarantees a ratio of at most k. The two algorithms we study in detail — Vertex Cover and metric TSP — are both 2-approximation algorithms for minimization problems, meaning their solutions are always
within a factor of 2 of optimal.
Prerequisite: What is a Matching?
A
matching in a graph is a set of edges that
do not share any endpoints — no vertex appears in more than one edge of the set. A
maximal matching is a matching where no more edges can be added without sharing an endpoint. (Note: "maximal" means you cannot add more; "maximum" means the largest possible — maximal is not necessarily maximum.)
Example: In the path graph 1—2—3—4—5, the edges {(1,2), (3,4)} form a maximal matching — no remaining edge (like (2,3) or (4,5)) can be added without reusing vertex 2 or 4.
The Proof Pattern (memorize this!)
Every approximation proof follows the same template:
Step 1: Find a
lower bound on OPT (the optimal solution). We usually can't compute OPT, but we can bound it.
Step 2: Show that the algorithm's solution is at most
ρ × (lower bound).
Step 3: Therefore, algorithm's solution ≤ ρ × OPT.
The art is in finding the right lower bound. For Vertex Cover, it's the size of a maximal matching. For TSP, it's the MST cost.
3 Vertex Cover — 2-Approximation
Problem: Given an undirected graph G = (V, E), find the smallest set of vertices C ⊆ V such that every edge has at least one endpoint in C.
Important: "Cover" Means Covering Edges, Not Vertices!
The name "vertex cover" can be misleading. The goal is
not to include all vertices — it is to select
enough vertices so that every
edge is "covered" (has at least one endpoint in the set). Vertices left out of the cover are perfectly fine, as long as no edge is left with
both endpoints missing from the cover.
Example: In the path 1—2—3—4—5, the set {2, 4} is a valid vertex cover with only 2 of the 5 vertices. Vertices 1, 3, and 5 are
not in the cover, but every edge still has at least one endpoint covered:
• Edge (1,
2) • Edge (
2,3) • Edge (3,
4) • Edge (
4,5)
Think of it as placing security cameras on some intersections (vertices) so that every road (edge) is watched by at least one camera. You don't need a camera on
every intersection — just enough to see every road.
Vertex Cover is NP-hard, but there's a beautifully simple 2-approximation:
ApproxVertexCover(G):
C = ∅ // our cover
E' = copy of E // uncovered edges
while E' is not empty:
pick any edge (u,v) from E'
C = C ∪ {u, v} // add BOTH endpoints
remove all edges incident to u or v from E'
return C
Why This is a 2-Approximation
Let A be the set of edges we picked. These edges form a
matching — no two share an endpoint (because when we pick (u,v), we remove all edges touching u and v).
Lower bound on OPT: Each edge in A must be covered, and no two edges in A share a vertex, so the optimal cover needs at least |A| vertices (one per edge in A).
Our algorithm: We add 2 vertices per edge in A, so |C| = 2|A|.
Therefore: |C| = 2|A| ≤ 2 × OPT. Our cover is at most
twice the optimal size!
Example
Consider a path graph: 1—2—3—4—5.
• Algorithm picks edge (1,2): adds {1,2} to cover, removes edges (1,2) and (2,3).
• Picks edge (3,4): adds {3,4}, removes (3,4) and (4,5).
• No uncovered edges left. Cover = {1, 2, 3, 4}, size = 4.
• Optimal cover: {2, 4}, size = 2.
• Ratio: 4/2 = 2. Exactly at the worst-case guarantee!
Try it yourself: In the tool below, select Vertex Cover and load different graph presets. Step through and watch edges being picked and vertices being added to the cover. The optimal cover size is shown for comparison!
4 Traveling Salesman — MST-Based 2-Approximation
Problem: Given n cities with pairwise distances, find the shortest tour visiting every city exactly once and returning to the start.
What is a Minimum Spanning Tree (MST)?
A
spanning tree of a connected graph is a subgraph that connects
all vertices using exactly
n − 1 edges and contains
no cycles. A
Minimum Spanning Tree (MST) is the spanning tree whose total edge weight is the smallest possible.
Example: Given 4 cities A, B, C, D with weighted edges, the MST picks the cheapest set of 3 edges that still connects all 4 cities without forming a loop.
Key property: The MST is the cheapest way to keep all vertices connected — any other spanning tree costs at least as much. This makes the MST cost a useful
lower bound in approximation proofs.
Well-known algorithms for computing MSTs include
Prim's algorithm (grow the tree one vertex at a time, always picking the cheapest edge to an unvisited vertex) and
Kruskal's algorithm (sort all edges by weight and add them one by one, skipping any edge that would create a cycle). Both run in polynomial time.
Prerequisite: What is DFS (Depth-First Search)?
DFS stands for
Depth-First Search — a graph traversal algorithm that explores as
deep as possible along each branch before backtracking. Starting from a root vertex, DFS visits a neighbor, then that neighbor's neighbor, and so on, going deeper until it reaches a dead end, then backs up and tries the next unvisited neighbor.
Example: In a tree A—B, A—C, C—D, starting at A: DFS might visit A → B (dead end, backtrack to A) → C → D (dead end, backtrack to C, then A). Done.
Key property for TSP approximation: When DFS walks through a tree, it traverses each edge
exactly twice — once going down, once coming back up. This is why the DFS walk of an MST costs exactly 2 × cost(MST).
TSP is NP-hard. With the triangle inequality (direct path is never longer than any detour: d(u,w) ≤ d(u,v) + d(v,w)), we get a 2-approximation:
ApproxTSP(G):
1. Compute a Minimum Spanning Tree (MST) of G
2. Do a DFS walk of the MST (visits each edge twice)
3. Shortcut: skip already-visited cities
return the resulting Hamiltonian cycle
Wait — The MST Is Not a Tour! Why Use It?
This is a common and important question. The MST has
no cycle and the salesman
cannot travel along it as a tour — it is not a solution to TSP. So why do we use it?
The MST is used as a
mathematical lower bound, not as the answer itself. Here is the key reasoning:
• The optimal TSP tour is a
cycle through all n cities.
• If you
remove any one edge from that cycle, the cycle breaks open into a
path — and a path through all n vertices is a spanning tree.
• Since the MST is the
cheapest possible spanning tree, its cost must be
less than or equal to the cost of that path, which is less than the cost of the full tour.
• Therefore:
cost(MST) ≤ cost(OPT tour).
We then use the MST as a
skeleton to build an actual tour: walk around the MST (DFS), which costs 2 × MST, then shortcut to get a valid tour. The MST itself is never the answer — it is the
tool that lets us both construct and analyze the approximation.
Why This is a 2-Approximation
Lower bound: cost(MST) ≤ cost(OPT) (as explained above).
DFS walk: Traverses each MST edge twice → cost = 2 × cost(MST).
Shortcutting: Triangle inequality → skipping visited cities never increases distance → tour ≤ 2 × cost(MST).
Therefore: cost(tour) ≤ 2 × MST ≤ 2 × OPT.
The Three Steps Visualized
Step 1 — MST: Find minimum spanning tree (e.g., using Prim's algorithm).
Step 2 — Full walk: DFS from root. The walk visits: A → B → A → C → D → C → A. Each MST edge traversed twice.
Step 3 — Shortcut: Skip repeated visits: A → B → C → D → A. This is our tour!
The shortcutting step is where the triangle inequality is essential — going directly from B to C is no worse than B → A → C.
Without Triangle Inequality: No Approximation Possible!
If distances don't satisfy the triangle inequality,
no polynomial-time algorithm can achieve any constant approximation ratio for TSP (unless P = NP). This is because general TSP can encode the
Hamiltonian Cycle (HC) problem — deciding whether a graph contains a cycle that visits every vertex exactly once — and approximating within any polynomial factor would solve HC exactly.
Try it yourself: In the tool below, select TSP (MST-Based). Watch the MST being built edge by edge, then the DFS walk, and finally the shortcut tour. Compare the tour cost with the MST cost!
5 Set Cover — Greedy ln(n) Approximation
Problem: Given a universe U = {1, 2, ..., n} and a collection of sets S₁, S₂, ..., Sₖ, find the fewest sets whose union is U.
GreedySetCover(U, S):
covered = ∅
chosen = []
while covered ≠ U:
pick Si that covers the most uncovered elements
chosen.append(Si)
covered = covered ∪ Si
return chosen
Approximation Ratio: O(ln n)
The greedy algorithm uses at most
H(max|S_i|) × OPT sets. Let's unpack this notation:
•
|S_i| = the
number of elements in set S_i (its size).
•
max|S_i| = the size of the
largest set in the collection. If the biggest set has 8 elements, then max|S_i| = 8.
•
H(k) = the
k-th harmonic number: H(k) = 1 + 1/2 + 1/3 + ... + 1/k ≈ ln k (the natural logarithm of k).
• So
H(max|S_i|) = the harmonic number evaluated at the size of the largest set. For example, if the largest set has 6 elements: H(6) = 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 ≈ 2.45.
Putting it together: the greedy algorithm uses at most
H(max|S_i|) × OPT sets — roughly
ln(largest set size) times the optimal number of sets.
This is essentially the best possible! Unless P = NP, no polynomial algorithm can achieve a ratio better than (1 − ε) ln n for any ε > 0.
Why H(max|S_i|) × OPT? — The Intuition
The key idea is a clever
cost accounting trick. Instead of paying "1" for each set we pick, we
spread the cost of each set evenly across the new elements it covers:
When the greedy algorithm picks a set that covers
k new elements, we charge each of those elements
1/k. The total cost of all sets chosen equals the total charge across all elements.
Now consider any single element e. What is the
most e can be charged across the whole algorithm? Suppose e first appears in a set of size k (the largest set containing e). At that moment, e
might not be picked — maybe a bigger set is chosen first. But each round, the number of uncovered elements in the set containing e can only
shrink. So the charges e could receive over successive rounds are at most:
1/k, 1/(k-1), 1/(k-2), ..., 1/2, 1/1
This sums to
H(k) = 1 + 1/2 + ... + 1/k — the k-th harmonic number, where k ≤ max|S_i| (the size of the largest set).
The Proof in Three Steps
Step 1 — Charge distribution: When greedy picks a set covering k new elements, charge each new element 1/k. Total charges = number of sets picked (each set costs 1, spread over its new elements).
Step 2 — Per-element bound: Each element e is charged at most H(k) in total, where k is the size of the largest set containing e. In the worst case, k = max|S_i|, so each element is charged at most H(max|S_i|).
Step 3 — Relate to OPT: The optimal solution also covers every element, using OPT sets. Each element in the universe belongs to at least one set in the optimal solution. We can "assign" each element's charge to the optimal set that contains it. Each optimal set receives at most H(max|S_i|) charge per element it contains. But we don't even need to count that precisely — the total charge across
all n elements is at most n × H(max|S_i|), and since OPT covers all n elements using OPT sets, the greedy cost (= total charge) is at most:
Greedy sets ≤ H(max|S_i|) × OPT
Since H(k) ≈ ln k and k ≤ n, this gives an
O(ln n) approximation ratio.
Worked Example — Charge Accounting
U = {1,2,3,4,5,6}, S₁={1,2,3}, S₂={2,4,5}, S₃={4,5,6}, S₄={1,6}. Optimal = 2 sets (S₁ ∪ S₃ = U).
Round 1: Greedy picks S₁ (covers 3 new elements: {1,2,3}). Charge each element 1/3.
Charges so far: 1→1/3, 2→1/3, 3→1/3
Round 2: S₂ covers 2 new (4,5), S₃ covers 3 new (4,5,6), S₄ covers 1 new (6). Greedy picks S₃ (most new). Charge each 1/3.
Charges so far: 4→1/3, 5→1/3, 6→1/3
Total: 2 sets picked = optimal! Maximum charge on any element = 1/3. Largest set has 3 elements, so H(3) = 1 + 1/2 + 1/3 ≈ 1.83. The bound says greedy ≤ 1.83 × 2 = 3.67 sets. We used 2, well within the bound.
Example — When Greedy Is Suboptimal
See the
"Greedy suboptimal" preset in the interactive tool below (10 elements, 5 sets).
U = {1,...,10}, S₁={1,2,3,4,5}, S₂={6,7,8,9,10}, S₃={1,2,6,7}, S₄={3,4,8,9}, S₅={5,10,1,6}.
Optimal: S₁ ∪ S₂ = U (2 sets). But greedy picks S₁ (5 new), then S₃ or S₄ (each covers only 2 new from the other half), requiring
3 sets total. Ratio = 3/2 = 1.5.
☆ The Common Thread — Greedy Algorithms
All three approximation algorithms above share the same underlying strategy: they are all greedy algorithms.
What is a Greedy Algorithm?
A
greedy algorithm builds a solution step by step, making the
locally optimal choice at each step — the choice that looks best
right now — without ever going back to reconsider previous decisions.
Greedy algorithms are
fast (typically polynomial time) and
simple to implement. For some problems they find the exact optimum (e.g., Prim's algorithm for MST,
Dijkstra's algorithm for shortest paths — which greedily visits the closest unvisited vertex to find the shortest path from a source to all other vertices). For NP-hard problems they cannot find the exact optimum in general, but they often achieve
provably good approximations.
Are the Exact (Original) Solutions Also Greedy? No!
The exact algorithms that find the
perfect optimal answer use fundamentally different strategies — and that is precisely why they are so slow:
Exact Vertex Cover — Brute-force enumeration: Try
every possible subset of vertices (2ⁿ of them) and check which is the smallest valid cover. This is exhaustive search, not greedy — it considers all possibilities before deciding.
Exact TSP — Permutation search / Dynamic programming: The brute-force approach tries all n! orderings of cities. The Held-Karp algorithm uses
dynamic programming (DP) — it stores solutions to subproblems in a table and builds up the optimal answer by combining them. DP is the
opposite of greedy: it considers
all choices at each step and picks the globally best combination, rather than committing to a local choice.
Exact Set Cover — Subset enumeration: Try every possible combination of the m available sets (2ᵐ combinations) and return the smallest one that covers the universe. Again, exhaustive search — no local decisions, just try everything.
The key insight:
greedy algorithms are fast because they commit to local choices and never look back. Exact algorithms are slow because they
explore all possibilities to guarantee the global optimum. Approximation algorithms accept a slightly worse answer in exchange for the speed of greedy decision-making.
The Greedy Strategy in Each Approximation
Vertex Cover: At each step, pick
any uncovered edge and greedily add both endpoints. Never reconsider — once a vertex is in the cover, it stays. The greedy choice here is simple but effective: adding both endpoints guarantees maximum coverage per decision.
TSP (MST-Based): The MST itself is built by a greedy algorithm (Prim's: always add the cheapest available edge). The tour is then derived by a greedy DFS traversal with shortcuts — always visit the next unvisited city.
Set Cover: At each step, greedily pick the set that covers the
most uncovered elements. This is the classic "greedy by largest marginal gain" strategy.
Side-by-Side: Exact vs. Greedy Approximation
| Exact (Original) | Greedy Approximation |
|---|
| Strategy | Try all possibilities | Make one local choice, move on |
| Backtracking? | Yes — explores and compares | No — never reconsiders |
| Time | Exponential (2ⁿ, n!) | Polynomial (n², n log n) |
| Answer quality | Perfect (global optimum) | Good (within factor ρ of optimum) |
| Practical for large n? | No | Yes |
Why Do Greedy Algorithms Give Good Approximations?
Because each greedy step makes a "reasonable" local choice, the total cost never drifts too far from optimal. This
bounded greediness can always be related back to a lower bound on OPT (matching for Vertex Cover, MST for TSP, harmonic analysis for Set Cover) — the same
proof pattern introduced in Section 2. This technique is central to
combinatorial optimization — the branch of mathematics and computer science concerned with finding the best solution from a finite (but typically enormous) set of possibilities.
6 Inapproximability — Limits of Approximation
Not all NP-hard problems can be approximated equally well. Before reading the table below, here are some terms you'll encounter:
Terminology for This Section
Metric TSP vs.
General TSP: Metric TSP is the version of TSP where distances satisfy the triangle inequality (the direct route is never longer than a detour).
General TSP has no such restriction — distances can be arbitrary. Metric TSP can be approximated; general TSP cannot.
Christofides' algorithm (1976): An improved approximation algorithm for metric TSP that achieves a
3/2-approximation (better than the 2-approximation we studied). It builds an MST, then adds a
minimum-weight perfect matching on the odd-degree vertices to create an Eulerian graph, and finally shortcuts the Eulerian circuit into a Hamiltonian cycle. For decades it was the best known result for metric TSP.
UGC (Unique Games Conjecture): A widely believed (but unproven) conjecture in computational complexity theory, proposed by Subhash Khot in 2002. If true, it implies that many approximation ratios we currently achieve are the
best possible — for example, it would prove that no polynomial-time algorithm can beat the 2-approximation for Vertex Cover.
MAX-3SAT: Given a Boolean formula in 3-CNF form (a conjunction of clauses, each with exactly 3 literals), find an assignment of variables that
satisfies the maximum number of clauses. A simple random assignment satisfies 7/8 of clauses on average, and remarkably, no polynomial-time algorithm can do better (unless P = NP).
| Problem | Best Known Ratio | Can We Do Better? |
|---|
| Vertex Cover | 2 | Likely not below 1.36 (UGC: not below 2) |
| Metric TSP | 3/2 (Christofides) | Breakthrough in 2020: 3/2 − ε |
| Set Cover | ln n | No! Cannot beat (1−ε)ln n |
| General TSP | None! | No constant ratio possible |
| MAX-3SAT | 7/8 | No (optimal under UGC) |
The PCP Theorem (1992) — A Landmark Result
PCP stands for
Probabilistically Checkable Proofs. The PCP Theorem shows that for many problems, even
approximating the optimal solution is NP-hard. This means there are fundamental barriers to approximation — not just a lack of clever algorithms, but actual impossibility results. For example, it is NP-hard to approximate Max-3SAT within a ratio better than 7/8 (matching the random algorithm!).
7 Interactive Tool
1. Select an algorithm from the dropdown.
2. Click a Quick Example or the inputs will use the default graph.
3. Click Build Steps, then Step or Play.
4. Watch the graph/set visualization update step by step with color-coded vertices and edges.
Teaching Tip
Start with
Vertex Cover on the "Path graph" preset — it's the simplest and shows the 2x worst case clearly. Then move to
TSP to show MST → tour conversion. Finish with
Set Cover to show the greedy strategy.
You've completed the lecture notes!
You now understand: why approximation is needed, approximation ratios, Vertex Cover 2-approximation, MST-based TSP 2-approximation, Greedy Set Cover, and inapproximability. Scroll down to experiment!