Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Christofides Algorithm

Graph Algorithm

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
Time Complexity
Time Complexity (category)
Polynomial Time -- O(n^k) 1
Classification
Design Technique
Heuristic or Approximation 1
Connections

Credited To

Nicos Christofides, Pioneers
Source Christofides Algorithm (Wikipedia)

In Field

Algorithms and Complexity Theory, Fields
Source Christofides Algorithm (Wikipedia)

Invented By

Nicos Christofides, Pioneers
Source Christofides Algorithm (Wikipedia)

Uses Design Technique

Approximation Algorithms, Concepts
Heuristics, Concepts
Sources
1. Christofides Algorithm (Wikipedia)
  • Wikipedia infobox: time complexity polynomial
    polynomial
  • Wikipedia: design technique heuristic-approximation
    heuristic-approximation
  • Credited To: Nicos Christofides, Lead section
    is named after Nicos Christofides and Anatoliy Serdyukov
  • Invented By: Nicos Christofides, Lead section
    is named after Nicos Christofides and Anatoliy Serdyukov
  • In Field: Algorithms and Complexity Theory, Lead sentence
    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).
  • In Group: Traveling Salesman Tour Algorithms, Lead
    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).
View the Source
Wikidata: Christofides Algorithm
Wikidata Q498144, class allow-list match (w-wdresolver-0926)View the Source
Christofides Algorithm (Wikipedia)
https://en.wikipedia.org/wiki/Christofides_algorithm
Quote, 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.
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.