47.04.08 · theoretical-cs / 04-algorithms-analysis

Approximation Algorithms: Vertex Cover, TSP, and Set Cover

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Cormen, Leiserson, Rivest and Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 35; Vazirani 2001 Approximation Algorithms (Springer) Ch. 1-2, 15 (tight analysis of greedy Set Cover, LP rounding, primal-dual methods)

Intuition Beginner

When a problem is NP-hard, we cannot find the exact optimal solution efficiently. But we can often find a solution that is provably close to optimal. An approximation algorithm runs in polynomial time and guarantees its output is within a known factor of the best possible answer.

Think of packing a suitcase. Finding the absolute optimal arrangement is hard. But you can guarantee fitting at least half of what the optimal arrangement would hold, using a simple strategy: just keep adding the largest item that fits. This is not perfect, but it is good, and you can prove exactly how good.

Three classic problems illustrate the range of what approximation can achieve. Vertex Cover has a simple 2-approximation: repeatedly pick an edge, add both its endpoints to the cover, and remove all edges touching them. Metric TSP has a 3/2-approximation via Christofides' clever construction combining a minimum spanning tree with a perfect matching. Set Cover has a logarithmic approximation via the greedy strategy. Each algorithm is simple, but proving its guarantee requires careful comparison against an unknown optimum.

Visual Beginner

Vertex Cover 2-approximation on a path graph:

  (a)---(b)---(c)---(d)---(e)

Step 1: Pick edge (b,c), add {b,c} to cover, remove all edges touching b or c
  Remaining: (a)  (d)---(e)

Step 2: Pick edge (d,e), add {d,e} to cover, remove all edges touching d or e
  Remaining: (a)

Cover = {b, c, d, e} — size 4
OPT = {b, d} — size 2
Ratio: 4/2 = 2 (matches the guarantee)

Problem	Approximation ratio	Technique	Hardness threshold
Vertex Cover	2	Maximal matching	1.36 (or 2 - eps under UGC)
Metric TSP	3/2	Christofides (MST + matching)	123/122 (recent)
General TSP	None (no constant factor)	—	Unapproximable
Set Cover	ln n	Greedy (most uncovered first)	(1 - eps) ln n

Worked example Beginner

We run the 2-approximation for Vertex Cover on a small graph. The graph has 4 vertices ${1, 2, 3, 4}$ and edges ${(1, 2), (2, 3), (3, 4)}$ (a path).

Step 1. Pick the first edge $(1, 2)$ . Add both endpoints: cover $= {1, 2}$ . Remove edges $(1, 2)$ and $(2, 3)$ (both touch vertex 1 or 2). Remaining edges: ${(3, 4)}$ .

Step 2. Pick edge $(3, 4)$ . Add both endpoints: cover $= {1, 2, 3, 4}$ . No edges remain.

The algorithm returns a vertex cover of size 4. The optimal cover is ${2, 3}$ of size 2 (vertices 2 and 3 touch every edge). The ratio is $4/2 = 2$ , matching the guarantee exactly.

For a better result, note that we could have just picked edges greedily and kept only one endpoint per edge—but that loses the guarantee. The 2-approximation is simple and provably correct because every edge in the matching must have at least one endpoint in any cover, and we pick both.

Check your understanding Beginner

Formal definition Intermediate+

Definition (approximation algorithm). Let $Π$ be an NP-optimisation problem with objective function $v a l$ . A polynomial-time algorithm $A$ is an $α$ -approximation for $Π$ (minimisation) if for every instance $I$ , $v a l (A (I)) \leq α \cdot O P T (I)$ . For maximisation, $v a l (A (I)) \geq α \cdot O P T (I)$ .

Definition (Vertex Cover). Given an undirected graph $G = (V, E)$ , find a minimum subset $C \subseteq V$ such that for every edge $(u, v) \in E$ , ${u, v} \cap C \neq = \emptyset$ .

Definition (Metric TSP). Given a complete graph $G = (V, E)$ with edge weights $w : E \to R^{+}$ satisfying the triangle inequality ( $w (u, v) \leq w (u, x) + w (x, v)$ for all $u, v, x$ ), find a Hamiltonian cycle of minimum total weight.

Definition (Set Cover). Given a universe $U = {1, \dots, n}$ and a collection $S = {S_{1}, \dots, S_{m}}$ of subsets of $U$ with $⋃_{i} S_{i} = U$ , find the smallest sub-collection $C \subseteq S$ with $⋃_{S \in C} S = U$ .

Counterexamples to common slips

"An approximation algorithm with ratio 2 always finds a solution of size exactly twice the optimum." The ratio is an upper bound. The algorithm can do better on specific instances.
"General TSP can be approximated within some constant factor." Without the triangle inequality, TSP cannot be approximated within any polynomial-time computable function unless P = NP, by reduction from Hamiltonian cycle.
"The greedy Set Cover algorithm is optimal among all polynomial-time algorithms." It achieves ratio $H_{n} \approx ln n$ , and no polynomial-time algorithm does better than $(1 - ε) ln n$ unless P = NP (Dinur-Steurer 2014). So it is essentially optimal, but the match is up to the $1 - ε$ factor.

Key theorem with proof Intermediate+

Theorem (2-approximation for Vertex Cover). The maximal-matching algorithm for Vertex Cover returns a cover of size at most $2 \cdot O P T (G)$ .

Proof. The algorithm repeatedly picks an arbitrary uncovered edge $(u, v)$ , adds both $u$ and $v$ to the cover $C$ , and removes all edges incident to $u$ or $v$ . It terminates when no edges remain.

Correctness. Every edge is either picked (and both endpoints are in $C$ ) or removed because one of its endpoints was picked with another edge. So every edge has at least one endpoint in $C$ .

Approximation ratio. Let $M$ be the set of edges picked by the algorithm. These edges form a matching (no two share a vertex) because after picking an edge, we remove all incident edges. So $∣ C ∣ = 2∣ M ∣$ .

Every edge in $M$ must have at least one endpoint in any vertex cover (even the optimal one), and since the edges in $M$ are disjoint (no shared vertices), each requires a distinct vertex in the cover. Therefore $O P T \geq ∣ M ∣$ , which gives $∣ C ∣ = 2∣ M ∣ \leq 2 \cdot O P T$ . $□$

Bridge. The maximal-matching algorithm is the foundational reason Vertex Cover is approximable within factor 2: the matching provides a dual lower bound on the optimum through the LP relaxation, and this builds toward the LP-rounding perspective where the same factor emerges from rounding fractional solutions. This is exactly the pattern that appears again in Set Cover where the greedy algorithm's ratio matches the integrality gap of the LP, and it generalises to the primal-dual method that unifies many approximation algorithms. The central insight is that a combinatorial lower bound (matching for Vertex Cover, frequency counting for Set Cover) paired with a greedy algorithm gives a provable ratio, and putting these together with the hardness bounds from 47.03.06 shows that for Vertex Cover the gap between 2-approximation and hardness is either small (1.36 under PCP) or zero (2 - eps under UGC).

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Christofides' algorithm for Metric TSP: (1) compute a minimum spanning tree $T$ , (2) find a minimum-weight perfect matching $M$ on the odd-degree vertices of $T$ , (3) combine $T \cup M$ into an Eulerian graph, find an Euler tour, and shortcut repeated vertices. Prove this gives a 3/2-approximation.

Hint

Bound $w (T) \leq O P T$ and $w (M) \leq O P T /2$ using the triangle inequality.

Answer

The MST weight $w (T)$ is at most $O P T$ : removing any edge from the optimal TSP tour gives a spanning tree, so $w (T) \leq O P T$ . Let $O$ be the set of odd-degree vertices in $T$ ; $∣ O ∣$ is even. The optimal TSP tour, restricted to the vertices in $O$ in tour order, gives two perfect matchings (alternating edges). The cheaper one has weight at most $O P T /2$ . Since $M$ is the minimum-weight perfect matching on $O$ , $w (M) \leq O P T /2$ . The Euler tour of $T \cup M$ has weight $w (T) + w (M) \leq O P T + O P T /2 = 3 O P T /2$ . Shortcutting (using the triangle inequality) can only decrease the weight. So the final tour has weight at most $3 O P T /2$ . Rubric: full credit for bounding both the MST and matching weights.

Exercise 5 (medium, symbolic).

Prove that the greedy algorithm for Set Cover achieves approximation ratio $H_{d}$ where $d = max_{i} ∣ S_{i} ∣$ is the size of the largest set.

Hint

Charge the cost of each greedy choice to the newly covered elements, and bound the total charge using the harmonic series.

Answer

Let $k$ be the number of sets in the greedy solution. At step $j$ , the greedy algorithm picks a set covering $c_{j}$ new elements at cost 1. The per-element cost at step $j$ is $1/ c_{j}$ . Since $c_{j}$ is the maximum number of uncovered elements any set can cover at step $j$ , and $O P T$ must cover all elements, the "effective cost" charged to each element $e$ covered at step $j$ is at most $1/ c_{j}$ . The number of uncovered elements when $e$ is covered is at least $c_{j}$ , so there are at most $n$ uncovered elements before step $j$ and at least $1$ covered element per step. The key bound: element $e$ is covered when at most $n$ elements remain uncovered, and the greedy choice covers at least $c_{j}$ of them, so the charge to $e$ is at most $1/ c_{j} \leq 1/ ⌈ n_{remaining} \cdot O P T_{frac} / k_{opt} ⌉$ . The standard analysis shows the total charge per element is at most $H_{d} / O P T$ per set in the optimal solution. Summing over all elements: $greedy cost \leq H_{d} \cdot O P T$ where $d = max_{i} ∣ S_{i} ∣$ . Rubric: full credit for the charging argument and the harmonic bound.

Exercise 7 (hard, symbolic).

Show that the integrality gap of the Vertex Cover LP relaxation is at most 2 and at least $2 - o (1)$ . That is, the ratio $O P T_{I P} / O P T_{L P}$ is between $2 - o (1)$ and 2 for all instances.

Hint

The upper bound follows from LP rounding. For the lower bound, consider the complete bipartite graph $K_{n, n}$ .

Answer

Upper bound: The LP-rounding algorithm proves $O P T_{I P} \leq 2 \cdot O P T_{L P}$ (Exercise 3).

Lower bound: Consider $K_{n, n}$ with bipartition $(A, B)$ where $∣ A ∣ = ∣ B ∣ = n$ . The optimal vertex cover is $2 n - 1$ (take all of one side minus one vertex, plus one from the other side) or $n$ (take either side). Actually, $O P T_{I P} = n$ (either $A$ or $B$ is a minimum cover). The LP relaxation assigns $x_{v} = 1/2$ for all $v$ , giving $O P T_{L P} = n$ . So the integrality gap is $n / n = 1$ , which is not the right example.

Consider instead the odd cycle $C_{2 k + 1}$ . $O P T_{I P} = k + 1$ (any vertex cover of an odd cycle needs more than half the vertices). The LP assigns $x_{v} = 1/2$ for all $v$ , giving $O P T_{L P} = (2 k + 1) /2$ . The ratio is $(k + 1) / ((2 k + 1) /2) = 2 (k + 1) / (2 k + 1) \to 2$ as $k \to \infty$ . So the integrality gap approaches 2 from below. Rubric: full credit for the odd cycle example showing the gap approaches 2.

Exercise 8 (hard, symbolic).

Prove that the greedy algorithm for Set Cover is essentially optimal: no polynomial-time algorithm can achieve an approximation ratio of $(1 - ε) ln n$ for any $ε > 0$ unless P = NP.

Hint

This is the result of Dinur and Steurer (2014), improving Feige (1998). Sketch the reduction structure.

Answer

Feige (1998) proved that Set Cover cannot be approximated within $(1 - ε) ln n$ for any $ε > 0$ unless $N P \subseteq D T I M E (n^{O (l o g l o g n)})$ . Dinur and Steurer (2014) strengthened this to unless P = NP.

The reduction starts from a $(1, 1 - ε)$ -gap label cover instance (from the PCP theorem with Raz's parallel repetition). Each label is encoded using a partition system: for each label $a \in [R]$ , create a partition of $[n]$ into $k$ parts. A Set Cover instance is built where: the universe consists of all partition elements, and the sets correspond to label-assignment pairs. If the label cover instance is satisfiable (YES), a cover of size $k$ exists (one set per partition). If not (NO), any cover must have size at least $k \cdot (1 - ε) ln n$ , because covering all elements of the partition system requires the harmonic number factor. This gives a gap of $(1 - ε) ln n$ . Rubric: full credit for describing the partition-system reduction and the gap amplification.

Exercise 9 (hard, symbolic).

A weighted Set Cover instance has universe $U = {1, 2, 3, 4, 5}$ , sets $S_{1} = {1, 2, 3}$ with weight 3, $S_{2} = {3, 4, 5}$ with weight 3, $S_{3} = {1, 4}$ with weight 2, $S_{4} = {2, 5}$ with weight 2, $S_{5} = {1, 2, 3, 4, 5}$ with weight 6 $. R u n t h e g r ee d y a l g or i t hman d co m p a r e i t scos tt o$ OPT$. What is the approximation ratio achieved?

Answer

Greedy picks by cost per uncovered element (weight / new elements covered).

Step 1: $S_{1}$ costs $3/3 = 1$ per element, $S_{2}$ costs $3/3 = 1$ , $S_{5}$ costs $6/5 = 1.2$ , $S_{3}$ costs $2/2 = 1$ , $S_{4}$ costs $2/2 = 1$ . Ties: pick $S_{1}$ . Covered: ${1, 2, 3}$ , cost 3.

Step 2: Remaining elements ${4, 5}$ . $S_{2}$ covers 2 new at cost $3/2 = 1.5$ , $S_{3}$ covers 1 new at cost $2/1 = 2$ , $S_{4}$ covers 1 new at cost $2/1 = 2$ , $S_{5}$ covers 2 new at cost $6/2 = 3$ . Pick $S_{2}$ . Covered: all, cost 3 + 3 = 6.

$O P T$ : Pick $S_{3}$ and $S_{4}$ : cost $2 + 2 = 4$ . Or pick $S_{1}$ and $S_{2}$ : cost 6. So $O P T = 4$ .

Ratio: $6/4 = 1.5$ . With $d = 5$ and $H_{5} \approx 2.28$ , the guarantee allows up to $4 \times 2.28 = 9.12$ , so the greedy solution of cost 6 is well within the guarantee.

Lean formalization Intermediate+

Mathlib has no formalization of approximation algorithms, approximation ratios, or the analysis of specific approximation algorithms. A SetCover.greedy definition with a proof that it achieves ratio $H_{d}$ would require the harmonic number bound, LP integrality gap analysis, and the dual-fitting proof technique. The Vertex Cover 2-approximation via maximal matching could be formalised using Mathlib's SimpleGraph and Matching structures, but the connection to the LP relaxation and integrality gap is absent. This unit ships without a lean_module.

Advanced results Master

Three results extend the basic approximation framework in different directions.

Result 1 (primal-dual method). The LP-rounding approach for Vertex Cover can be replaced by a purely combinatorial primal-dual algorithm that achieves the same 2-approximation without solving an LP. The algorithm maintains a dual feasible solution (a matching) and raises dual variables until a primal feasible solution (a cover) is obtained. This method generalises to many problems: Steiner Forest, Facility Location (constant-factor), and $k$ -Median (constant-factor). The primal-dual method is the workhorse of approximation algorithm design because it avoids the overhead of LP solving while retaining the same approximation guarantee ^{[Vazirani Ch. 15]}.

Result 2 (PTAS and FPTAS). Some problems admit a Polynomial-Time Approximation Scheme (PTAS): for every $ε > 0$ , a $(1 + ε)$ -approximation runs in time $n^{O (1/ ε)}$ . Euclidean TSP has a PTAS (Arora 1998, Mitchell 1999). Knapsack has an FPTAS (Fully Polynomial-Time Approximation Scheme) running in time $O (n / ε)$ . The boundary between PTAS-existence and hardness is characterised by the theory of APX-completeness: a problem is APX-hard if it admits no PTAS unless P = NP ^{[CLRS Ch. 35]}.

Result 3 (recent improvements in TSP). Karlin, Klein and Oveis Gharan (2020) proved a $(3/2 - 1 0^{- 36})$ -approximation for Metric TSP, breaking the 3/2 barrier of Christofides' 1976 algorithm. This was improved to $3/2 - 1 0^{- 12}$ by subsequent work. The technique uses the max-entropy sampling distribution on the spanning tree polytope and analyses the expected parity correction. The result is a landmark because the 3/2 barrier stood for over four decades ^{[CLRS Ch. 35 notes]}.

Synthesis. Approximation algorithms provide the algorithmic counterpart to the hardness results of 47.03.06: where the PCP theorem establishes that no algorithm can cross certain ratio barriers, approximation algorithms show how close to those barriers we can get. The central insight is that the gap between the algorithmic ratio and the hardness bound defines the frontier of our understanding—Vertex Cover sits at ratio 2 with hardness at 1.36 (or $2 - ε$ under UGC), Set Cover has a tight match at $ln n$ , and Metric TSP sits at 3/2 with hardness at 123/122. This builds toward the randomised methods of 47.05.04 where randomness provides additional power for approximation in counting problems, and this is exactly the pattern that generalises from combinatorial optimisation to the broader landscape of NP-hard problems. Putting these together with the PCP theorem yields the full picture of what is efficiently computable.

Full proof set Master

Proposition 1 (greedy Set Cover approximation ratio). The greedy algorithm for Set Cover achieves an approximation ratio of $H_{d} = \sum_{i = 1}^{d} 1/ i$ where $d = max_{i} ∣ S_{i} ∣$ .

Proof. Let the greedy algorithm pick sets $S_{j_{1}}, S_{j_{2}}, \dots, S_{j_{k}}$ in order. At step $t$ , it picks the set covering the most uncovered elements; let $c_{t}$ be the number of newly covered elements at step $t$ . Assign a price of $1/ c_{t}$ to each element covered at step $t$ . The total cost of the greedy solution equals the total price assigned: $\sum_{t = 1}^{k} c_{t} \cdot (1/ c_{t}) = k$ , but we want to compare costs, not just count sets.

For weighted Set Cover, assign price $w (S_{j_{t}}) / c_{t}$ to each element covered at step $t$ . The total greedy cost is $\sum_{t = 1}^{k} w (S_{j_{t}}) = \sum_{t = 1}^{k} c_{t} \cdot (w (S_{j_{t}}) / c_{t}) = \sum_{e \in U} p r i ce (e)$ .

Consider any set $S_{i}$ in the optimal solution. When $S_{i}$ is examined at step $t$ , at most $∣ S_{i} ∣$ of its elements are uncovered. Since greedy picks the set with the most uncovered elements, $c_{t} \geq ∣ S_{i} ∖ (covered by step t) ∣$ . Each uncovered element of $S_{i}$ at step $t$ receives price at most $w (S_{i}) /∣ S_{i} ∖ covered ∣$ .

The total price charged to elements of $S_{i}$ is at most $w (S_{i}) \cdot H_{∣ S_{i} ∣} \leq w (S_{i}) \cdot H_{d}$ . Since every element belongs to some set in the optimal cover: $\sum_{e} p r i ce (e) \leq \sum_{S_{i} \in O P T} w (S_{i}) \cdot H_{d} = H_{d} \cdot O P T$ . So the greedy cost is at most $H_{d} \cdot O P T$ . $□$

Proposition 2 (no constant-factor approximation for general TSP). For any polynomial-time computable function $f$ , TSP without the triangle inequality cannot be approximated within factor $f (n)$ unless P = NP.

Proof. Reduce Hamiltonian Cycle to TSP. Given graph $G = (V, E)$ , create a TSP instance on $V$ with $w (u, v) = 1$ if $(u, v) \in E$ and $w (u, v) = 2$ otherwise. If $G$ has a Hamiltonian cycle, the optimal TSP tour has weight $n$ . If not, every tour must use at least one non-edge, giving weight at least $n + 1$ . An algorithm distinguishing these cases solves Hamiltonian Cycle.

For stronger inapproximability: set non-edge weights to $n \cdot f (n)$ . Then YES instances have $O P T = n$ and NO instances have $O P T \geq n \cdot f (n)$ . An $f (n)$ -approximation would return a tour of cost at most $f (n) \cdot n$ in the YES case and at least $n \cdot f (n)$ in the NO case, distinguishing them. This works for any polynomial-time computable $f$ . $□$

Connections Master

47.02.03 — NP-completeness is the starting point: every problem discussed here is NP-hard to solve exactly, and approximation is the response to that intractability.
47.04.01 — Amortised analysis techniques appear in the running-time analysis of approximation algorithms, particularly for data-structure-based implementations of greedy algorithms.
47.03.06 — Hardness of approximation provides the matching lower bounds: Vertex Cover at 1.36, Set Cover at $(1 - ε) ln n$ , and general TSP at no constant factor.
47.05.04 — FPRAS extends approximation to counting problems where the output is a numerical estimate rather than a combinatorial structure.
47.05.05 — Derandomisation techniques can convert randomised approximation algorithms into deterministic ones with the same guarantee.

Historical & philosophical context Master

The study of approximation algorithms began in the 1960s and 1970s with the greedy algorithm for Set Cover (Johnson 1974, Lovász 1975) and the 2-approximation for Vertex Cover. Christofides' 3/2-approximation for Metric TSP appeared in 1976 and stood as the best known ratio for 44 years until Karlin, Klein and Oveis Gharan's 2020 improvement.

The field matured through the lens of LP relaxations: the work of Hochbaum (1982) on LP rounding for Vertex Cover, the primal-dual framework of Bar-Yehuda and Even (1981), and the comprehensive treatment by Vazirani (2001). The tight analysis of greedy Set Cover (achieving $H_{n}$ and hardness at $(1 - ε) ln n$ ) represents one of the few cases where the algorithmic upper bound matches the complexity-theoretic lower bound up to lower-order terms ^{[CLRS Ch. 35]}.

The philosophical lesson is that NP-hardness does not mean we must give up entirely: approximation algorithms provide rigorous, practical solutions with provable quality guarantees. The question shifts from "can we solve it?" to "how close can we get?", and the answer is often surprisingly good.

Bibliography Master

@book{cormen2022introduction,
  author    = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@book{vazirani2001approximation,
  author    = {Vazirani, Vijay V.},
  title     = {Approximation Algorithms},
  publisher = {Springer},
  year      = {2001},
}
@article{christofides1976worst,
  author  = {Christofides, Nicos},
  title   = {Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem},
  journal = {Technical Report, Carnegie Mellon University},
  year    = {1976},
}
@article{karlin2020slightly,
  author  = {Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan},
  title   = {A Slightly Better Approximation Algorithm for the Traveling Salesman Problem},
  journal = {Proceedings of the 53rd ACM Symposium on Theory of Computing},
  year    = {2021},
  pages   = {32--45},
}
@article{feige1998threshold,
  author  = {Feige, Uriel},
  title   = {A Threshold of $\ln n$ for Approximating Set Cover},
  journal = {Journal of the ACM},
  volume  = {45},
  number  = {4},
  pages   = {634--652},
  year    = {1998},
}

Prerequisites

47.04.01 pending
47.02.03 pending

Tier anchors

beginner: Cormen, Leiserson, Rivest and Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 35 (approximation algorithms guarantee solutions within a known factor of the optimum)
intermediate: Cormen, Leiserson, Rivest and Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 35 (2-approximation for Vertex Cover, Christofides algorithm for Metric TSP, greedy ln n-approximation for Set Cover)
master: Cormen, Leiserson, Rivest and Stein 2022 Introduction to Algorithms 4e (MIT Press) Ch. 35; Vazirani 2001 Approximation Algorithms (Springer) Ch. 1-2, 15 (tight analysis of greedy Set Cover, LP rounding, primal-dual methods)

References

Cormen, T. H., Leiserson, R. L., Rivest, R. L. and Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Chapter 35 presents approximation algorithms for NP-hard optimisation problems, defining an $α$ -approximation algorithm as a polynomial-time algorithm that produces a solution within factor $α$ of the optimum; the chapter proves the 2-approximation for Vertex Cover by maximal matching (pick both endpoints of each edge in the matching, yielding a cover of size at most $2 \cdot O P T$ since any cover must include at least one endpoint of each matched edge), the $3/2$ -approximation for Metric TSP via Christofides algorithm (build an MST, find a minimum-weight perfect matching on the odd-degree vertices, then Euler-tour-shortcut), and the $H_{n} \approx ln n$ greedy approximation for Set Cover (repeatedly pick the set covering the most uncovered elements); the analysis of greedy Set Cover shows the approximation ratio is $H (max_{i} ∣ S_{i} ∣)$ where $H (k) = \sum_{j = 1}^{k} 1/ j$ is the harmonic number.
Vazirani, V. V. — Approximation Algorithms · Springer (2001). Chapters 1-2 develop the framework of approximation algorithms including LP rounding for Vertex Cover (relax the integer program to a linear program, solve the LP, round variables $\geq 1/2$ up to 1), achieving the same factor-2 guarantee via a fundamentally different technique; Chapter 15 analyses the greedy Set Cover algorithm and proves its ratio is optimal under P $\neq =$ NP via the reduction of Feige (1998).

Estimated time

beginner: 15m
intermediate: 40m
master: 90m