报告人：洪绫珠研究员 台湾成功大学
报告题目：Approximation algorithms and inapproximability of hub allocation problems
时 间：2016-07-21 (星期四) 10:30 ~ 12:30
地 点：仓山校区成功楼601会议室
主 办：数学与计算机科学学院，福建省网络安全与密码技术重点实验室
参加对象：学院相关专业教师和研究生
报告摘要：Given a metric graph G = (V, E, w), a center, and an integer k, the Star k-Hub Center Problem is to find adepth-2 spanning tree T of G rooted by c such that c has exactly k children and the diameter of T is minimized. Those children of c in T are called hubs. A similar problem called the Single Allocation k-Hub Center Problem is to find a spanning subgraph H* of G such that (i)is a clique of size k in H*; (ii)forms an independent set in H*; (iii) eachis adjacent to exactly one vertex in C*; and (iv) the diameter D(H*) is minimized. The vertices selected in C* are called hubs and the rest of vertices are called non-hubs. Both Star k-Hub Center Problem and Single Allocation k-Hub Center Problem are NP-hard and have applications in transportation system, telecommunication system, and post mail system. In this talk, I will give 5/3-approximation algorithms for both problems. Moreover, I will give a proof to show that for any, the Star k-Hub Center Problem has no ( )-approximation algorithm unless P = NP. Under the assumption P ≠ NP, for any the Single Allocation k-Hub Center Problem has no ( )-approximation algorithm.
专家简介：Ling-Ju Hung received her Bachelor’s Degree in Applied Mathematics from National Chung Hsing University, Taiwan, in 2001 and her M.S. and Ph.D. Degrees in Computer Science and Information Engineering from National Chung Cheng University, Taiwan in 2003 and 2012, respectively.She became a postdoctoral research fellow in Department of Computer Science and Information Engineering, Hung Kuang University, Taiwan during 2012—2015. She is currently a postdoctoral research fellow at the Department of Computer Science and Information Engineering, National Cheng Kung University. Her research interests include the design and analysis of fixed-parameter algorithms, exact algorithms, and approximation algorithms.
