2014/10/07(二) 資訊工程研討的演講，歡迎聽講！

演講者: Sun-Yuan Hsieh,Distinguished Professor with the Department of Computer Science of National Cheng Kung University

Tainan, Taiwan

時間: 10/07(二) 13:20~15:10

地點: 綜合一館地下室 101室 (AB101)

主持人：王昱舜教授

主題: The Internal Steiner Tree Problem: Hardness and Approximations

大綱:

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 finding an internal Steiner tree T whose total cost  is the minimum. In this talk, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present 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, we present a -approximation algorithm for the problem.

簡介:

Sun-Yuan Hsieh received the PhD degree in computer science from National Taiwan University, Taipei, Taiwan, in June 1998. He then served the compulsory two-year military service. From August 2000 to January 2002, he was an assistant professor at the Department of Computer Science and Information Engineering,   National Chi Nan University. In February 2002, he joined the Department of Computer Science and Information Engineering, National Cheng Kung University, and now he is a distinguished professor. He received the 2007 K. T. Lee Research Award, President's Citation Award (American Biographical Institute) in 2007, Engineering Professor Award of Chinese Institute of Engineers (Kaohsiung Branch) in 2008, National Science Council’s Outstanding Research Award in 2009, IEEE Outstanding Technical Achievement Award (IEEE Tainan Section) in 2011, Outstanding Electronic Engineering Professor Award of Chinese Institute of Electrical Engineers in 2013, and Outstanding Engineering Professor Award of Chinese Institute of Engineers in 2014. He is Fellow of the British Computer Society (BCS). His current research interests include design and analysis of algorithms, fault-tolerant computing, bioinformatics, parallel and distributed computing, and algorithmic graph theory.