Christofides algorithm
Approximation for the travelling salesman problem / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Christofides algorithm?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality).[1] It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and Anatoliy I. Serdyukov (Russian: Анатолий Иванович Сердюков); the latter discovered it independently in 1976 (but the publication is dated 1978).[2][3][4]