“最小曼哈顿网络问题”被攻克

村长小麦

复旦大学昨天传来消息，该校计算机学院大三学生郭泽宇关于最小曼哈顿网络问题的论文被美国ACM学会主办的第25届计算几何国际会议录用，文章同时作为最佳论文之一被邀请投稿到会议特刊(DCG)。这意味着计算几何领域十余年来未决的重要猜想被这位年仅20岁的本科生成功解决。
　　最小曼哈顿网络问题是计算机学院朱洪教授给自己指导的本科生们所开设的题目，在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应用。记者 张骞　 转自新闻晚报

村长小麦

最小Manhattan网络问题是近年来受到广泛关注的计算几何和组合最优化问题。在大规模集成!电路（VLSI）设计、分布式算法、计算生物学、网络设计、城市规划等领域发挥着越来越大的作用。

　　给定平面上一个点集T，其Ma
nhattan网络由水平和垂直线段组成，并满足T中任意两点间在网络中存在Manhattan路径。可知 Manhattan网络即为L1-范数下给定点集的一个1-spanner。更一般的概念称作geometric spanner或k-spanner，由于具有良好的性质，其应用十分广泛，包括邻近问题（proximity problems）的求解、机器人的运动规划、通信网络的可靠性等等。在本问题中，要求Manhattan网络中线段总长度最短，即以最小的代价构造给定点集的Manhattan网络。此外，F. Lam  等人在生物序列比对问题中应用了Manhattan网络的近似算法，显著减小了搜索空间。这显示了最小Manhattan网络问题在计算生物学中的应用。由此可见，这一问题的研究无论在理论还是实际中都有十分重要的意义。

　　最小Manhattan网络问题由J. Gudmundsson, C. Levcopoulos和G. Narasimhan于1999年最早提出。之后，许多学者研究并给出了这一问题多
项式时间近似算法。之前通过组合方法设计的最佳近似算法（3-近似）由 M. Benkert  等人在2004年给出。2005年，V. Chepoi [2] 等人提出了基于线性规划的2-近似算法，这是目前所知关于这一问题的最好近似度。

　　2009年6月复旦大学计算机学院大三学生郭泽宇关于“最小曼哈顿网络问题”的论文被第25届计算几何国际会议录用，文章同时作为最佳论文之一被邀请投稿到会议特刊DiscreteandComputationalGeometry(DCG)。这意味着计算几何领域十年来的重要猜想被这位年仅20岁的本科生成功解决。计算几何国际会议是计算几!何领域最高级别的会议，这一会议，中国内地数学家已经阔别了整整十八年。

村长小麦

最近,复旦大学计算机学院三年级学生郭泽宇破解了一个猜想——根据曼哈顿城市地图抽象出来的数学问题:最小曼哈顿网络问题。他的论文被计算几何界最高层次的学术会议——第25届计算几何国际会议录用,同时作为最佳论文被会议特刊约稿。

    给定平面上的一个点集,构造总长度

    最小的网络,使得任意两点之间都有长度最短的路径相连——学者们给它起名“最小曼哈顿网络问题”。这十多年来,因证明计算极其复杂,这个“最小”只是猜想。

    郭泽宇的成果令国际计算几何界欣喜,也为复旦大学的本科生学术研究计划提供了成功的范例。

    1998年,在李政道先生倡导和设立的“莙政基金”支持下,复旦大学资助优秀本科学生尽早接触学术研究的计划正式实施。借鉴“莙政基金”的实施经验,复旦陆续开展了“望道项目”和“曦源项目”,结合“国家大学生创新性实验计划”和“上海市大学生创新活动计划”,形成了一个层次分明、申请时间灵活、申请形式多样的本科生学术研究资助平台。

    郭泽宇的研究项目正是“莙政项目”。最小曼哈顿网络问题在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应用,但它是国际计算几何领域没有解决的“猜想”。面对郭泽宇选择的这个难题,基于鼓励本科生创新和支持年轻人“闯劲”的考虑,评审专家们决定给予莙政学者项目资助。

    据了解,从1998年到2008年,复旦大学已有1556位学生获得资助开展研究,其项目学科涵盖了医学、工学、理学、文学、教育学等多个领域。在郭泽宇当初的项目申请书上,作为推荐老师的中科院院士陆汝钤表达过的观点,正好可以用来评价复旦大学的本科生学术研究资助计划:通过这一方式可以使许多学生脱颖而出,走上从事科学研究的道路。

村长小麦

	最小曼哈顿网络问题，是1999年提出的世界级计算几何重要猜想。2009年6月，被上海复旦大学仅20岁的本科生郭泽宇成功解决。他的关于“最小曼哈顿网络问题”的论文被第25届计算几何国际会议录用，文章同时作为最佳论文之一被邀请投稿到会议特刊Discrete and Computational Geometry(DCG)。 　　 　　最小曼哈顿网络问题，在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应用。自曼哈顿网络的复杂度问题于1999年提出至今，没有人知道问题的答案，从而使得对这一问题的研究成为计算几何中最为重要的几个未解决问题之一。

村长小麦

复旦大学2009年6月21日传来消息，该校计算机学院大三学生郭泽宇关于最小曼哈顿网络问题的论文被美国ACM学会主办的第25届计算几何国际会议录用，文章同时作为最佳论文之一被邀请投稿到会议特刊(DCG)。

　　这意味着计算几何领域十余年来未决的重要猜想被这位年仅20岁的本科生成功解决。

　　2008年6月，郭泽宇申请了复旦大学本科生学术研究资助计划的“莙政”项目。最小曼哈顿网络问题是计算机学院朱洪教授给自己指导的本科生们所开设的题目。

　　郭泽宇大胆地选择了这一问题作为项目攻克对象。这既让朱洪教授和博士研究生孙贺这两位项目指导老师感到欣喜，也让“莙政”学者评审专家们捏了一把汗。基于鼓励本科生创新和支持年轻人闯劲的考虑，郭泽宇最终得到了资助。经过200多个日夜的思考和探索，这一难题终于被他找到突破口。

村长小麦

补充一点

最近,复旦大学计算机学院三年级学生郭泽宇破解了一个猜想——根据曼哈顿城市地图抽象出来的数学问题:最小曼哈顿网络问题。他的论文被计算几何界最高层次的学术会议——第25届计算几何国际会议录用,同时作为最佳论文被会议特刊约稿。


    给定平面上的一个点集,构造总长度


    最小的网络,使得任意两点之间都有长度最短的路径相连——学者们给它起名“最小曼哈顿网络问题”。这十多年来,因证明计算极其复杂,这个“最小”只是猜想。


    郭泽宇的成果令国际计算几何界欣喜,也为复旦大学的本科生学术研究计划提供了成功的范例。


    1998年,在李政道先生倡导和设立的“?政基金”支持下,复旦大学资助优秀本科学生尽早接触学术研究的计划正式实施。借鉴“?政基金”的实施经验,复旦陆续开展了“望道项目”和“曦源项目”,结合“国家大学生创新性实验计划”和“上海市大学生创新活动计划”,形成了一个层次分明、申请时间灵活、申请形式多样的本科生学术研究资助平台。


    郭泽宇的研究项目正是“?政项目”。最小曼哈顿网络问题在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应用,但它是国际计算几何领域没有解决的“猜想”。面对郭泽宇选择的这个难题,基于鼓励本科生创新和支持年轻人“闯劲”的考虑,评审专家们决定给予?政学者项目资助。


    据了解,从1998年到2008年,复旦大学已有1556位学生获得资助开展研究,其项目学科涵盖了医学、工学、理学、文学、教育学等多个领域。在郭泽宇当初的项目申请书上,作为推荐老师的中科院院士陆汝钤表达过的观点,正好可以用来评价复旦大学的本科生学术研究资助计划:通过这一方式可以使许多学生脱颖而出,走上从事科学研究的道路。

村长小麦

复旦学子解决计算几何难题 辅导教授否认“国际悬疑”  
年仅20岁的复旦大学大三学生郭泽宇和25岁的博士研究生孙贺共同完成的关于“最小曼哈顿网络问题算法和复杂性”的论文，近日被第25届计算几何国际大会（SCG）录用，并受邀出席大会作报告。消息传出后，“复旦学生破解世界级几何猜想”的消息立刻被各媒体争相报道。

　　昨天，该校计算机学院朱洪教授在接受本报记者采访时表示：“其实，这谈不上世界级难题。值得关注的是年轻人静下心来搞科研的心态。”与此同时，社会学专家也表示，动辄“世界级”，体现了部分媒体的浮躁心态。

　　年轻的奇迹阔别18年，内地青年重回SCG

　　在位于丹麦奥胡思大学湖岸剧院的第25届计算几何国际大会上，复旦大学20岁的大三学生郭泽宇代表论文作者向大会做了报告，报告题目是“最小曼哈顿网络是NP-C”。

　　这意味着，计算几何领域这一10年未决的重要问题由这两位来自中国的年轻人成功解决了，而此前，中国内地研究机构阔别SCG大会讲台也已经18年了。

饶为市

中国的年轻的数学天才真是了不起。