クリストフィードのアルゴリズム
クリストフィードのアルゴリズムの近似度を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/2となる場合が存在する。