克里斯托菲德斯算法

克里斯托菲德斯算法(Christofides algorithm) 是旅行商问题在度量空间（即距离对称且满足三角不等式）上的一个近似算法。 该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。尼科斯·克里斯托菲德斯(Nicos Christofides) 于1976年首次发表了这个算法，故以他的名字命名之。 截至2017年，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。

近似比

算法所生成的解相对最优解有3/2的近似比。下给出简要证明。
令 C 为图上的最优旅行商回路。注意到，删除 C 上的一条边将产生原图上的一棵生成树，其总权重至少为最小生成树的总权重，亦即 w(T) ≤ w(C)。接下来，给O中的顶点编号，编号顺序依据回路C 上的顶点顺序。再将 C 做划分，得到两个边集：其一包含所有起始点为奇数编号的边，另一个则包含所有起始点为偶数编号的边。这两个边集各对应于 O 上的一个完美匹配，且匹配的总边权不超过边集的总边权。
因为两个边集是 C 的划分，二者中的某一个至多有 C 总边权的一半，因而其对应匹配的总边权不超过 C 总边权的一半。因为没有比最小完美匹配更小的匹配，所以 w(M) ≤ w(C)/2。 T 和 M 的权重总和也就是欧拉回路的权重总和，也就是至多3w(C)/2。由于做选取近道操作并不增加权重，所有最终输出的总边权也不超过 3w(C)/2.

下界

存在使得克里斯托菲德斯算法近似比任意接近3/2的输入。
一类满足条件的输入由 n 个顶点组成，满足最优环路上边的权重都为 1，且在最优环路上相隔一条边的边都有权重 1 + ε，其中 ε 是一个足够小的正数。未由上述定义给出的权重由两点间的最短路径给出。
最小生成树可以从最优环路中构造，总长 n − 1。唯二的奇数度点是这棵树（此时也是条路径）的两个端点，其完美匹配仅由一条权重近似为 n/2 的单边构成。
生成树和这条单边的并集是一个回路，没有可能的近道(short-cutting)，且其总边权近似为 3n/2。 而问题的最优解是使用所有权重为1或 1 + ε 的边构造的环路，其总权重为 n + (n − 2)ε，对充分小的 ε 可以无限靠近于n。