クリストフィードのアルゴリズム

G = (V,w) について巡回セールスマン問題を考える。頂点集合を V、その完全グラフを G とし、G に含まれる全ての辺に対し定義される非負の重み集合を w とする。三角不等式より任意の3つの点 u, v, x に対し、w(uv) + w(vx) ≥ w(ux) が成立する。

以下に擬似コードを示す^[1]。

1. G の最小全域木 T を構築する。
2. T に含まれる奇数次の頂点集合を O とする。このとき、握手補題（英語版）より O は偶数個の頂点を持つ。
3. O に含まれる頂点によって与えられる誘導部分グラフにおいて最適マッチング M を探索する。
4. M と T の辺を統合し、すべての頂点が偶数次となる多重グラフ H を構築する。
5. H 内部でオイラー閉路を構成する。
6. 構成したオイラー閉路において、既に訪れた点を飛ばしながら辿る（近道）ことにより、ハミルトン閉路を形成する。

このアルゴリズムによって生成された解の重みは最適な解の重みに対し3/2以下である。証明のため、C を巡回セールスマン問題の最適解とする。最適解 C から辺を1つ削除すると全域木となり、その全域木の重みは（最小全域木の定義より）最小全域木の重みより小さくならないため、w(T) ≤ w(C) である。次に、O の頂点に対し、最適解の経路 C の順に番号を付け、C の順で奇数番目の辺の集合と、偶数番目の辺の集合の、2つの辺集合に分割する。それぞれの辺の集合は O の最適マッチングに対応し、それぞれの経路の2つの端点と一致する。そして、その最適マッチングの辺の重みは最適解 C によるものであるため、マッチングの重みは最適解の対応する辺の重み以上である。これらの2つの経路の集合は C の辺を2分割するため、経路の集合の1つは C の重みの半分以上であり、それに対応するマッチングは C の重みの半分以下である。最小重み最適マッチングは最小の重みを選択するアルゴリズムであるため、w(M) ≤ w(C)/2 が保証される。そして T と M の重みを足すことで、オイラー回路の重みが 3w(C)/2 以下であることがわかる。点を飛ばす処理（近道）によって、重みは増えないため、このアルゴリズムによって生成された経路の重みは最大 3w(C)/2 である^[1]。

クリストフィードのアルゴリズムの近似度を3/2まで限りなく近づけることができる頂点集合が存在する。そのような1つの入力はn 個の頂点によって形成される道に対し、1つの頂点まで辺の重みを1とし、道において2辺分離れた頂点を結ぶ辺の重みを 1 + ε とし（但し、ε は限りなく0に近い正の数とする）、残りの完全グラフの辺の重みは既に定義された部分グラフの最短経路の重みの和とする。このグラフで形成される最小全域木が重み1の n − 1 本の辺を持ち、ただ2つの奇数次の頂点を持つ。そしてその奇数次の頂点の最適マッチングは重みおよそ n/2 の1本の辺によって構築される。最小全域木と最適マッチングの辺を統合した経路は単純閉路であるため、近道は存在せず、重みの和はおよそ 3n/2 となる。 しかし、最適解は重み 1 + ε の n-2 本の辺と、道の端点の辺である重み1の2本の辺によって構成されるため、重みの和は n + (n − 2)ε となり、ε が十分小さい場合 n に近づく^[3]。したがって、近似度は3/2となる場合が存在する。