Gharan等人提出的新算法的近似解，先利用随机过程创建树，然后再将它转换成完整的往返旅程。
这种方法似乎很有前景，他们相信这是一种更好的算法，但严谨地证明出这种优越性并非易事。
2011年，Gharan等人成功证明，他们的新算法在“图形化”TSP上比克里斯托菲德斯算法更优。“图形化”TSP可以理解成TSP的一类特例，也就是城市之间的距离由一个网络（不一定包括所有连接）表示，每边长度相同。但他们一直没能将结果推广到一般性TSP中。
几年来，Gharan仍然在一直思考这个问题。他认为，数学中的多项式几何（geometry of polynomials）领域可能是解决问题的关键工具，但理论计算机界对这一数学领域知之甚少。Gharan在与Karlin共同指导研究生Klein时，他们决定共同推进对这个问题的研究。
在第一年里，他们先从一种简化版本入手。尽管困难重重，但他们开始对所用的工具有了感觉，尤其是多项式几何。
多项式是由常数和变量的幂运算等组合而成的表达式，比如x²y+2yz⁵。在TSP中，研究人员将一张城市地图提炼成一个多项式，其中每座城市之间的连接是一个变量，可以连接所有城市的每个树是一项。数值因数随后为这些项加权，反映出旅行售货员问题的分段解中每条边的值。
他们发现，这个多项式有一种迷人的性质，也就是“实稳定性”（real stability），也就是说，让多项式为零的复数永远不在复平面的上半部分。实稳定性带来的优势是，即使对多项式做出许多改变，它仍然有效。例如，当研究人员操控一些更简化的多项式时，他们操控的结果仍然具有实稳定性，这就为各种各样的技巧打开了大门。
这使得研究人员能够更好地处理一些问题。终于，在一份80多页的论文中，Karlin、Klein和Gharan证明出，10年前设计出的算法确实比克里斯托菲德斯算法要更好。新算法在克里斯托菲德斯算法（3/2近似比）的基础上，将近似比提高到了3/2 - 10⁻³⁶。
虽然这一微小的数字看似不足为道，但许多理论计算机学家相信，它突破了理论和心理上的僵局。研究人员希望，这能为进一步的提高开辟道路。
喜欢数学心请大家收藏：(m.mnowo.com)数学心迷你书窝更新速度全网最快。