The Christofides algorithm, also called the Christofides-Serdyukov algorithm, finds approximate solutions to the travelling salesman problem on instances where the distances between points form a metric space. It is an approximation algorithm guaranteeing a solution within one and a half times the length of the optimal tour, built by combining a minimum spanning tree with a minimum weight matching on the tree's odd degree vertices. Nicos Christofides published the algorithm in 1976, and Anatoliy Serdyukov discovered it independently the same year, publishing it in 1978.
Facts
Classification
Design TechniqueHeuristic or Approximation 1 Sources
1. Christofides Algorithm (Wikipedia)
https://en.wikipedia.org/wiki/Christofides_algorithmQuote, https://en.wikipedia.org/wiki/Christofides_algorithm
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 Serdyukov.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.