您当前的位置 :麻章新闻网 > 时政 > 上海交通大学在世界顶级计算机科学大会SODA上发表论文

上海交通大学在世界顶级计算机科学大会SODA上发表论文



9月16日,上海交通大学电子信息与电气工程学院ACM班(2011年并入上海交远学院)。 2010年学生刘经纬和林成玉参加了最先进的国际会议ACM-SIAM计算机科学算法研讨会。离职算法(SODA 2014)就业论文。他们的论文《A Simple FPTAS for Counting Edge Covers》与微软亚洲研究院的研究员Lu Pinyan博士合作,将于2014年1月的SODA会议上发表。

边缘覆盖(图形的边缘覆盖)是指图形边缘的集合,使得每个顶点在集合中具有至少一个邻居。这是图论中非常重要的概念,有许多应用。这里的问题是给出一个图表,计算它覆盖的不同边的数量。以前,仅对于最大为3的图形,存在多项式时间随机算法来近似该数字。本文给出了任何图的多项式时间近似方案(FPTAS),它完全解决了这个问题。本文中使用的相关衰减技术也是设计FPTAS以计算问题的有力工具。

这是交通大学计算机科学专业学生第二次在SODA上发表论文,也是本科生的第一篇SODA论文。 2012年9月,计算机科学系博士生张驰浩的论文被SODA2013录取,成为计算机科学学院第一篇SODA论文。

研究员吕平雁是论文的合作者,是致远学院计算机科学方向讲座组的成员。从2011年交大的兼职研究员和教授开始,陆丕炎博士在交通大学开设了本科算法课程,并为研究生和本科生开设了计算机理论研究。刘经纬和林成玉是算法课程的学生,他从大三开始就与算法相关的方向与他合作。张驰浩是博士。卢平雁导演的学生。

作者:

致远学院李兵