主讲人
Yonggang Jiang Max Planck Institute for Informatics 更多阅读 时间 2026年6月23日 星期二 上午 10:00-11:00 地点 星空手机站登录入口手机版登录104会议室
Abstract We will discuss recent algorithmic advances for fundamental graph problems, including negative-weight shortest paths, maximum flow, and minimum-cost flow. Classical textbook-style algorithms, such as Bellman-Ford and push-relabel, often lead to O(mn)-type running times. In recent years, however, there has been tremendous progress on these problems, with algorithms now approaching linear time. Biography Yonggang Jiang is a final-year PhD student at the Max Planck Institute for Informatics and an incoming Junior Fellow at ETH Zurich’s Institute for Theoretical Studies. His research focuses on the design and analysis of algorithms, particularly in graph algorithms, parallel algorithms, and distributed computing. He has coauthored over 20 publications in top venues, such as STOC, FOCS, SODA, PODC, and SPAA. His work has been recognized with a Google PhD Fellowship (2025) and a Distinguished Paper Award at SPAA 2025.
There are two major lines of work behind this progress: one based on continuous optimization, especially interior-point methods (IPMs), and another based on combinatorial techniques. This talk will focus on the latter. In particular, I will discuss two recent results that I coauthored:
- the first deterministic near-linear-time algorithm for negative-weight shortest paths;
- the first combinatorial algorithm for minimum-cost flow that is almost-linear time on dense graphs.
A common perspective behind these advances is lift-and-project: lift the problem to a graph with simpler structure, such as an acyclic graph, solve the problem there, and project the solution back to the original graph. I will explain how this viewpoint helps recent developments for path and flow problems, and discuss some open directions. 对照阅读
