Approximation algorithms¶
Part 5 of the course, volume 5 of the lecture notes: chapters 34–40.
Approximation algorithms: performance ratios and approximation schemes, with algorithms and worst-case analyses for knapsack, bin packing, the metric TSP and parallel machine scheduling, and the limits of approximation for vertex coloring, maximum clique and the general TSP.
Lecture notes (PDF) Exercises (PDF)
-
34. Principles of approximation algorithms
Approximation algorithms · Approximation schemes
Knapsack problems¶
-
35. Approximation algorithms for the knapsack problem
Notation · Split item and residual capacity · The greedy algorithm · The Ext-Greedy algorithm
Packing problems¶
-
36. Approximation algorithms for bin packing
Notation · The Next Fit · The Any Fit class · Half-full property
Coloring problems¶
-
37. Vertex coloring: limits of approximation
Notation · The VCP is not approximable · Special cases · Examples
Clique problems¶
-
38. Maximum clique: limits of approximation
Notation · The MCP is not approximable · Special cases · Example
Routing problems¶
-
39. The TSP: the general case and the metric case
The general TSP is not approximable · A special case: the metric TSP · The double tree and the Christofides algorithms · Structural properties
Scheduling problems¶
-
40. Approximation for P||Cmax
Notation · The algorithms \(LIST\) and \(LPT\) · A property of list scheduling · Performance guarantees