Approximation Algorithms¶
A course of the Operations Research and Mathematics series · all the courses
Teaching material conceived and developed by Fabio Furini, associate professor at DIAG, Sapienza University of Rome.
The course lecture notes, online: what an approximation algorithm guarantees and how to prove it; algorithms, worst-case analyses and tight instances for knapsack, bin packing, the metric TSP and parallel machine scheduling; approximation schemes; the limits of approximation for vertex coloring, maximum clique and the general TSP. With definitions, results with proofs, worked examples, exercises with solutions, Colab notebooks and interactive apps.
Prerequisites: Combinatorial Optimization Problems for the problems and Heuristic Algorithms for the algorithms analysed here (greedy, First Fit, LPT, nearest neighbour…).
Try it now¶
Christofides' algorithm on ten cities: the tour found over the optimal tour, with a ratio below the 3/2 guarantee. Press «Run» to replay the minimum spanning tree, the matching, the Eulerian circuit and the shortcuts, or switch to double tree.
The parts of the course¶
The chapters, by family of problems as in the menu: each card gives its chapter in the lecture notes.
-
1. Principles of approximation algorithms
Principles
Approximation algorithms · Approximation schemes
-
2. Approximation algorithms for the knapsack problem
Knapsack problems
Notation · Split item and residual capacity · The greedy algorithm · The Ext-Greedy algorithm
-
3. Approximation algorithms for bin packing
Packing problems
Notation · The Next Fit · The Any Fit class · Half-full property
-
4. Vertex coloring: limits of approximation
Coloring problems
Notation · The VCP is not approximable · Special cases · Examples
-
5. Maximum clique: limits of approximation
Clique problems
Notation · The MCP is not approximable · Special cases · Example
-
6. The TSP: the general case and the metric case
Routing problems
The general TSP is not approximable · A special case: the metric TSP · The double tree and the Christofides algorithms · Structural properties
-
7. Approximation for P||Cmax
Scheduling problems
Notation · The algorithms \(LIST\) and \(LPT\) · A property of list scheduling · Performance guarantees
Don't miss¶
-
Exercises with solutions
Exercises for every chapter, each with its worked solution that opens with a click.
-
Self-assessment quiz
A new mock exam at every start: 13 questions, 33 points, with the solution and the link to the notes. Downloads also has the full question bank.
-
Interactive lab
Apps running in the browser: move the parameters and watch the ideas of the course at work, one step at a time.
-
Lecture notes in PDF
Lecture notes, exercise books and slides in PDF, with the same numbering as the website.
-
Notebooks in Colab
The code of the course running in the browser, with nothing to install.
-
Full index
All the chapters with their sections on one page, and how each chapter is organized.
The series¶
All the courses of the series are built the same way: lecture notes online and in PDF, exercises with solutions, an interactive lab and self-assessment quizzes.
-
real numbers, functions, limits, derivatives and series, with interactive graphs
-
vectors, matrices, determinants, linear systems and eigenvalues, with the computation lab
-
number representation, pseudo-code, sorting and searching, analysis and recursive algorithms
-
polyhedra, the simplex algorithm, duality and the dual simplex, with the interactive lab
-
LP relaxation, valid inequalities, cutting planes, branch-and-bound and branch-and-cut
-
convex sets and functions, convex optimization problems, with interactive graphs
-
graphs, spanning trees, shortest paths, network flows, the network simplex and project management
-
Combinatorial Optimization Problems
knapsack, bin packing, coloring, TSP, scheduling and lot sizing: the problems, their formulations and ad hoc algorithms
-
principles and DP algorithms for knapsack, lot sizing, coin change and rod cutting
-
constructive heuristics, local search, metaheuristics and MIP heuristics for combinatorial optimization problems
-
Approximation Algorithms · this course
performance guarantees, approximation schemes and limits of approximation for combinatorial problems
-
linear programming models of managerial problems, solved with Python and Gurobi
-
nonlinear programming models, from portfolios to machine learning, with Python and Gurobi
-
integer linear programming models, from the formulation to the solution with solvers
Teaching material by Fabio Furini — DIAG, Sapienza University of Rome.
This website is also available in Italian.