肖鸣宇: 图多路分割问题的快速精确算法

肖鸣宇 (University of Electronic Science and Technology of China)

Time:

09:30-10:30 (Time in Beijing)
July 4, 2024 (Thursday)

Venue:

Host:

Nankai University （南开大学）

Abstract:

经典的最小割问题是通过删除图中最少的顶点将图中两个终端顶点分割开来，这个问题的一个自然推广就是将图中多个终端顶点相互分割开来，这就是图多路分割问题(The MultiwayCut Problem)。尽管最小割问题存在快速的多项式算法，但是当需要分割3个或者更多终端顶点的时候，这个问题就变成了NP难的。对图多路分割问题来说，经典的最大流最小割这一对偶性质不存在了，找到一个比简单穷举搜素算法更快的算法也不容易。在无向图上，图多路分割问题目前最好的精确算法可以做到 $1.4767^n$ 时间，其中n是图中顶点的个数。在有向图上是否存在比简单穷举算法 $2^n$ 时间更快的算法却一直是一个未解决的公开难题。本文将介绍在有向图上如何在 $1.9967^n$ 时间内解决图多路分割问题。

Speaker Bio:

肖鸣宇，现为电子科技大学计算机科学与工程学院教授，副院长算法与逻辑实验室执行主任;中国计算机学会理事、理论计算机科学专业委员会主任;国家级信息与网络安全虚拟仿真实验教学中心主任国家级计算机实验教学示范中心主任。致力于算法、计算理论、图论与图算法、机制设计与算法博弈论等方面的基础理论研究，为SAT、最大独立集等多个基本NP难问题设计了当前最佳的精确算法和参数算法;并将算法理论应用于人工智能、工业优化、计算经济、运筹学等领域中取得了显著成效。近年来在算法理论、人工智能基础算法领域顶级期刊和会议上以单独作者和主要作者发表论文超过150篇，撰写英文专著1部。主持国家级科研项目10余项。