题 目：The Internal Steiner Tree Problem: Hardness and Approximations

报告人：谢孙源，教授（台湾成功大学）

时 间：2014年10月28日（星期二） 下午 16:30－17:30

地 点：管理科研楼1208会议室

摘要：Given a graph G = (V, E) with a cost function c: E → R+ and a vertex subset R⊂V, an internal Steiner tree is a Steiner tree that contains all the vertices in R, and such that each vertex in R must be an internal vertex. The internal Steiner tree problem involves findingan internal Steiner tree T whose total cost is the minimum. This talk first shows that the internal Steinertree problem is MAX SNP-hard, then presents a (2ρ + 1)-approximation algorithm for solving the problem on complete graphs, where ρ is an approximation ratio for the Steiner tree problem. Currently, the best-known ρ is  . Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, this talk presents a 9/7-approximation algorithm for the problem.

报告人简介：台湾大学博士，成功大学特聘教授，制造资讯与系统研究所所长；研究方向涉及算法、图论、互连网络、多处理机系统、平行及分散系统、生物信息等领域，共发表94篇期刊和51篇会议论文，其中在IEEE Transactions 上的论文超过30篇；担任Theoretical Computer Science, Journal of Information Security，Journal of Supercomputing 等10多种国际专业杂志编委；荣获IEEE Outstanding Technical Achievement Award，英国资讯学会会士，成功大学教学杰出教师，台湾李国鼎研究奖，台湾杰出研究奖，台湾杰出电机工程教授奖和杰出资讯人才奖。

主办单位：
365英国上市官网
中科院吴文俊数学重点实验室
欢迎感兴趣的师生参加！