报告题目（title）：Approximation algorithms for the path partition problem on directed graphs
报告人（Speaker）： Guohui Lin（University of Alberta, Canada）
报告时间（Time）：2021年5月12日 上午 10:00
报告地点（Venue）：ZOOM会议号： 918 3617 8405；密码：107523
报告摘要（Abstract）：Given a directed graph G = (V, E), the k-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most k to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation and others.
Its special case on undirected graphs has received much attention recently, but the general directed version is seemingly untouched in the literature. We present the first k/2-approximation algorithm, for any k3, based on a novel concept of augmenting path to minimize the number of singletons in the partition. Then, for k = 3, we define the second novel kind of augmenting paths and propose an improved 13/9-approximation algorithm.
报告人简介：Dr. Guohui Lin is currently a Professor of Computing Science at the University of Alberta, with tenure. He was an Assistant and then an Associate Professor at the same university since 2001. He obtained his PhD degree in Computer Science, specialized in Combinatorial Optimization, in 1998 from the Chinese Academy of Sciences (Thesis Supervisor Dr. Ding-Zhu Du); and he obtained Master of Science and Bachelor of Science in Applied Mathematics in 1995 and 1993, respectively, from the Zhejiang University.
