你是一位辛苦而忙碌的推销员，需要穿梭在许多城市之间。假设现在你有一系列目的地城市需要逐一拜访，并最终返回你生活的那座起点城市。你已经做了充足的准备，知道任意两座城市之间的距离，那么，应当如何规划旅行路径，才能使得整个旅程最短呢？
虽然描述和理解起来并不复杂，但这绝不能算是一个简单的问题，尤其是当“城市”的数量远不止三五座，而是一个庞大的数字时，问题的复杂程度也可能变得超乎想象。
这个问题有个专属的名字，它通常被称为旅行推销员问题（travelling salesman problem， tsp），是理论计算机科学中一个最著名的存在已久的基本问题之一。理论计算机科学家为了检验有效计算的极限，对这一问题进行了反复研究。几十年来，它也激发了计算机科学中许多基础的进步，帮助阐释了线性规划等技术的能力。一些科学家甚至把探索tsp称为一种“瘾”。
tsp也并非单纯的“纸上谈兵”，而是具有广泛的实际意义，在物流、制造业，甚至dna测序中都有应用。在这些情况下，“城市”就代表着客户、dna片段等，而“城市间的距离”则可以指时间、距离、相似度等。
两年前，当nathan klein开始研究生学习时，他的导师anna karlin与shayan oveis gharan提出了这样一个规划——共同研究理论计算机科学中这个著名问题。klein的导师都认为，即使他们无法解决这个问题，klein也能在这个过程中学到很多东西。当时仍是研究生新生的klein同意了这个计划，他还不知道自己在接下来两年将会面临什么。
如今，在上传至预印本网站的一篇论文中，导师与klein终于实现了他们的目标，事实上，这也是计算机科学家近半个世纪以来一直所追求的——他们证明了找出tsp近似解的更优算法。
大多数计算机科学家相信，没有一种算法可以有效地为tsp所有可能的城市组合找到最优解。虽然如此，找到接近最优解的方法还是有可能的。
1976年，尼科斯·克里斯托菲德斯（nis christofides）提出了一种算法，可以有效地找到tsp的近似解，并保证这种近似解中的往返旅程最多比最优解长出50%（近似比不超过3/2）。这种算法利用了连接所有城市的最短“树”，也就是没有闭合回路的连接（或者叫“边”）网络，然后将这种树作为主干，随后添加额外的连接，将它转换成完整的往返路径。
这是一个简单的tsp例子，在这个例子中，最优解并不复杂。而克里斯托菲德斯算法会先找到连接所有城市的最短树，然后再将它转换成完整的往返旅程。
在任何往返旅程中，连接每座城市的边都必须是偶数条，这不难理解，因为每次到达后都会离开。事实证明反之亦然，也就是说，如果网络中的每