Everything About ___
Live briefing

Everything about Approximation algorithm

Class of algorithms that find approximate solutions to optimization problems

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. Wikipedia →

🧭 Start here: a 6-step reading path

  1. Read the overview: Approximation algorithmA 5-minute orientation
  2. Skim a recent paper: A review on Quantum Approximate Optimization Algorithm and its variantsInfluential work since 2022
  3. Pick up a classic book: Approximation, Randomization, and Combinatorial Optimization. Algorithms and TechniquesThe most-reprinted book on the subject
  4. Read the landmark paper: The AAA Algorithm for Rational ApproximationCited 453 times
  5. Go sideways: Semidefinite programmingA closely related topic
  6. Go sideways: Differential evolutionA closely related topic

📖 Definitions

Noun A method of finding a nearly optimal solution to an optimization problem that cannot be solved exactly within a reasonable time.

🗂️ The subject at a glance

  1. Introduction
  2. Algorithm design techniques
  3. A posteriori guarantees
  4. Hardness of approximation
  5. Practicality
  6. Structure of approximation algorithms
  7. Performance guarantees
  8. Epsilon terms

🏆 Landmark papers (most cited)

🆕 Influential since 2022

📚 Books worth reading

Ranked by number of editions on Open Library, a rough measure of how lasting a book is.

🔗 Related topics