小量变引起大质变，多项式几何助力旅行商问题研究取得突破性进展

选自quantamagazine作者：Erica Klarreich机器之心编译编辑：Panda旅行商问题也称最短路径问题，是指给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。自 1976 年 Nicos Christofides 提出了一种简单的近似方法之后，这一问题在几十年的时间里鲜有进展。直到最近，华盛顿大学的一个研究团队才最终证明十年前提出的一种方法能带来非常细微的提升。进展的量虽小，但却是在旅行商问题上迈出的一大步，也许更是未来进一步进展的突破口。本文将介绍这种突破性近似优化方法背后的故事。两年前，当 Nathan Klein 刚进入华盛顿大学研究生院时，他的导师提出了一个谦逊的培养计划：一起研究理论计算机科学领域一个最有名的待解决问题。他 ………………………………