Approximation algorithms for the path partition problem on directed graphs
- A+
：林国辉
：2021-06-02 10:00
：Zoom Meeting ID: 918 3617 8405 Pwd: 107523 （线上）
报告人：林国辉（University of Alberta）
时 间：6月2日上午10:00
地 点：Zoom Meeting ID: 918 3617 8405 Pwd: 107523 （线上）
内容摘要:
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 k > 3, 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.
联系人：刘龙城
