Downloads¶
The lecture notes and the exercise book in PDF, with the same numbering of definitions, theorems, examples and exercises as the website, the slides of the chapters and the Colab notebooks with the code of the algorithms. Text and figures are released under CC BY 4.0, the code under the MIT licence.
Lecture notes and exercise book¶
| Volume | Contents | Chapters | File |
|---|---|---|---|
| Lecture notes | 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. | 1–7 | PDF (1.1 MB) |
| Exercise book | Worked exercises on the chapters of Volume 1, approximation algorithms: each exercise is followed by its complete solution. | 1–7 | PDF (0.7 MB) |
Slides¶
The lecture slides, one PDF per chapter, with the same definitions and examples as the lecture notes.
| Chapter | Title | File |
|---|---|---|
| 1 | Principles of approximation algorithms | PDF (0.4 MB) |
| 2 | Approximation algorithms for the knapsack problem (1/2) | PDF (0.6 MB) |
| 2 | Approximation algorithms for the knapsack problem (2/2) | PDF (0.6 MB) |
| 3 | Approximation algorithms for bin packing | PDF (0.6 MB) |
| 4 | Vertex coloring: limits of approximation | PDF (0.4 MB) |
| 5 | Maximum clique: limits of approximation | PDF (0.3 MB) |
| 6 | The TSP: the general case and the metric case | PDF (0.5 MB) |
| 7 | Approximation for \(P\|C_{\max}\) | PDF (0.4 MB) |
Colab notebooks¶
The code of the algorithms, one notebook per chapter and per language, to run in Google Colab or to download (.ipynb links). How to use them: the notebooks page.
| Chapter | Python | C++ |
|---|---|---|
| 2. Approximation algorithms for the knapsack problem | ||
| 3. Approximation algorithms for bin packing |
Quiz question bank¶
All the self-assessment questions, by part and chapter, with the correct answer and the explanation; for the generated questions, whose numbers change at every start, a few examples.