座城市都有偶数条连接，那么网络中的连接一定能构成一个往返旅程。
连接所有城市的最短树则缺乏这种“偶数性”，因为位于分支末端的城市只存在一条连接。克里斯托菲德斯算法找到了最佳的方式，将拥有奇数条连接的城市相连，就让最短树变成了一个往返旅程。随后他证明，由此产生的往返旅程最多比最优解长50%。
克里斯托菲德斯算法是理论计算机科学中最著名的近似算法之一，它也成了不少教科书和课程中经常出现的最佳案例。但计算机科学家一直相信，应当存在比克里斯托菲德斯算法更优的近似算法。毕竟，克里斯托菲德斯算法虽然简单直观，但并非总是那么高效，因为连接城市的最短树或许并非可选择的最佳主干。比如，如果这个树有许多分支，那么分支末端的每座城市都需要与另一座城市相匹配，这可能会带来大量昂贵的新连接。
当时许多人认为，不久就会有人对克里斯托菲德斯的简单算法提出改进。但事情并没有这么简单。
直到10年前，gharan和他的博士导师以及合作者开始研究提高克里斯托菲德斯算法的可能。他们受到了另一种版本的tsp的启发。在这个版本中，你可以选择一种组合路径。例如，如果你想去a地，可以选择3/4的b到a的路径，加上1/4的c到a的路径。这种“分段版本”的问题虽然没有实际的物理意义，却能够有效地求解。对计算机科学家来说，它也可以作为对求解一般性tsp的一种思路引导。
因此，gharan等人没有选择连接所有城市的最短树，而是从一个精心筛选的集合中随机选择一个树。他们创建了新的算法，利用一种随机过程创建出树，在这样的树中，拥有奇数条连接的城市倾向于有邻近的“搭档”。接着再用类似克里斯托菲德斯算法的方式，将这些城市与其“搭档”相连，就能创造出一个完整的往返旅程。
gharan等人提出的新算法的近似解，先利用随机过程创建树，然后再将它转换成完整的往返旅程。
这种方法似乎很有前景，他们相信这是一种更好的算法，但严谨地证明出这种优越性并非易事。
2011年，gharan等人成功证明，他们的新算法在“图形化”tsp上比克里斯托菲德斯算法更优。“图形化”tsp可以理解成tsp的一类特例，也就是城市之间的距离由一个网络（不一定包括所有连接）表示，每边长度相同。但他们一直没能将结果推广到一般性tsp中。
几年来，gharan仍然在一直思考这个问题。他认为，数学中的多项式几何（geometry of polynomials）领域可能是解决问题的关键工具，但理论计算机界对这一数学领域知之甚少。gharan在与karlin共同指导研究生klein时，他们决定共同推进对这个问题的研究。
在第一年里，他们先从一种简化版本入手。尽管困难重重，