Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Christofides algorithm
open-in-new
<p> The Christofides algorithm or Christofides–Serdyukov algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for finding approximate solutions to the <a href="/facts/Travelling_salesman_problem/2WEKVLnV">travelling salesman problem</a>, on instances where the distances form a <a href="/facts/Metric_space/gnBBRXtc">metric space</a> (they are symmetric and obey the <a href="/facts/Triangle_inequality/KubLjkwr">triangle inequality</a>). It is an <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithm</a> that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after <a href="/facts/Nicos_Christofides/hU1Hn9Gq">Nicos Christofides</a> and Anatoliy Serdyukov (<a href="/facts/Russian_language/ETXrTgHV">Russian</a>: Анатолий Иванович Сердюков). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978. </p>