In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. An example of an approximation algorithm with a multiplicative guarantee is the Christofides-Serdyukov algorithm for the Travelling salesman problem. It provides a travelling salesman tour in a metric of length at most 3/2 times that of a shortest such tour. A classic example of approximation algorithm providing an additive guarantee is the constructive proof of Vizing’s theorem. It shows how to color the edges of an undirected graph with at most colors, where is the maximum degree of any node. Since every edge incident on a maximum-degree node must have a different color, the constructive proof of the theorem gives a polynomial-time algorithm that uses at most one additional color than the minimum needed. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.