Approximation Algorithms

Algorithms that find provably near-optimal answers to hard optimization problems in reasonable time, such as the Christofides algorithm, randomized rounding, polynomial-time approximation schemes and the nearest neighbour heuristic for the travelling salesman problem. An algorithm belongs here when its cited article calls it an approximation algorithm or approximation scheme. It excludes exact methods. A member is placed here by what its own cited article states about it, not by the name of the algorithm or by the uses it is put to today, so each entry sits in the group its source describes it as belonging to.