9月16日，上海交大致远学院计算机科学方向2010级学生刘景铖、林承宇收到来自计算机科学算法领域最顶级的国际会议ACM-SIAM Symposium on Discrete Algorithms(SODA 2014) 的论文录用信。他们与微软亚洲研究院主管研究员陆品燕博士合作的论文《A Simple FPTAS for Counting Edge Covers》将发表在2014年1月的SODA会议上。
Edge Cover，即一个图的边覆盖，指该图的一个边的集合使得每个顶点都至少有一条邻边在这个集合中。这是图论中一个很重要的概念，也有很多应用。这里的问题是给定一个图，要计算它的不同边覆盖的个数。之前只有对最大度不超过3的图，有一个多项式时间的随机算法去近似这个数。该论文给出了一个对于任意图的多项式时间的近似方案(FPTAS)，从而完全解决了这个问题。该论文用到的相关性衰减技术也是计数问题设计FPTAS的强有力工具。
这是上海交大计算机专业学生第二次在SODA发表论文，也是本科生的第一篇SODA论文。2012年9月，计算机系在读博士生张驰豪的论文被SODA2013录用，成为学校计算机系第一篇SODA论文。
论文的合作者陆品燕研究员是我校致远学院计算机科学方向讲座教授组成员。从2011年受聘上海交大兼职研究员及讲席教授开始，陆品燕博士就在上海交大开设本科生的算法课程，并指导研究生及本科生计算机理论方向的科研。刘景铖和林承宇是他算法课上的学生，并从大三开始跟他一起做算法相关方向研究。张驰豪是陆品燕指导的博士研究生。
