最小曼哈顿网络问题的背景

发布网友发布时间：2022-04-28 20:59

共1个回答

热心网友时间：2022-06-23 04:32

最小曼哈顿网络问题，是在1999年提出的世界级计算几何重要猜想。1999年，J. Gudmundsson, C. Levcopoulos与G. Narasimhan最早提出了最小曼哈顿网络问题。之后，许多学者研究并给出这一问题多项式时间近似算法。之前通过的组合方法设计的最佳近似算法（3-近似）是由M. Benkert等人在2004年给出。2005年，V. Chepoi等人提出基于线性规划的2-近似算法，这是所知关于这一问题最好近似度。
2009年6月，被上海复旦大学仅20岁的本科生郭泽宇成功解决。他的关于“最小曼哈顿网络问题”的论文被第25届计算几何国际会议录用，文章同时作为最佳论文之一被邀请投稿到会议特刊Discrete and Computational Geometry(DCG)。