计算机科学家在旅行商问题上取得突破

当 Nathan Klein 开始读博时，他的两位导师提议共同研究理论计算机科学领域的一个著名难题。导师们认为，即使未能解决这个难题，在此过程中 Klein 将会学到很多东西。Klein 接受了，初生牛犊不怕虎，作为一年级的博士生，他并不知道会遇到多大的困难。Klein 和他在华盛顿大学的导师 Anna Karlin 和 Shayan Oveis Gharan 刚刚发表了一篇论文，报告了他们在困扰了计算机科学家近半个世纪的旅行商问题上取得的突破，找到了一种更好的方法去寻找近似解。