Full index¶ All the pages of the website, in the order of the menu: the chapters with their sections and the other pages. Chapters¶ 1. Principles of approximation algorithms · Exercises 1.1 Approximation algorithms 1.2 Approximation schemes 1.3 Typical mistakes 1.4 In summary Knapsack problems¶ 2. Approximation algorithms for the knapsack problem · Exercises 2.1 Notation 2.2 Split item and residual capacity 2.3 The greedy algorithm 2.4 The Ext-Greedy algorithm 2.5 The \(H^2\) algorithm 2.6 The \(H^{\ell}\) algorithm 2.7 The Basic-FPTAS algorithm 2.8 Performance guarantees 2.9 Absolute performance guarantee 2.10 Typical mistakes 2.11 In summary Packing problems¶ 3. Approximation algorithms for bin packing · Exercises 3.1 Notation 3.2 The Next Fit 3.3 The Any Fit class 3.4 Half-full property 3.5 Performance guarantees 3.6 Typical mistakes 3.7 In summary Coloring problems¶ 4. Vertex coloring: limits of approximation · Exercises 4.1 Notation 4.2 The VCP is not approximable 4.3 Special cases 4.4 Examples 4.5 Sources 4.6 Typical mistakes 4.7 In summary Clique problems¶ 5. Maximum clique: limits of approximation · Exercises 5.1 Notation 5.2 The MCP is not approximable 5.3 Special cases 5.4 Example 5.5 Sources 5.6 Typical mistakes 5.7 In summary Routing problems¶ 6. The TSP: the general case and the metric case · Exercises 6.1 The general TSP is not approximable 6.2 A special case: the metric TSP 6.3 The double tree and the Christofides algorithms 6.4 Structural properties 6.5 Performance guarantees 6.6 Sources 6.7 Typical mistakes 6.8 In summary Scheduling problems¶ 7. Approximation for P||Cmax · Exercises 7.1 Notation 7.2 The algorithms \(LIST\) and \(LPT\) 7.3 A property of list scheduling 7.4 Performance guarantees 7.5 Sources 7.6 Typical mistakes 7.7 In summary Other pages¶ Exercises Lab Downloads Colab notebooks Self-assessment