AI engineering glossary · Data structures algorithms
What is approximation algorithm?
Approximation algorithm: An algorithm for a hard optimisation problem that runs in polynomial time and comes with a proven guarantee on how far its answer can be from the optimum, such as within a factor of 2. This differs from a heuristic, which has no such guarantee.
Approximation algorithm: an example
A well-known simple method for vertex cover picks both ends of unmatched edges and returns a cover at most twice the size of the best one.
Related terms
More Data structures algorithms terms
Where you learn it
Approximation algorithm is part of the AI Engineering Program, which teaches it with notes, a hands-on lab and an exam. The first lesson is free.