Theory Lunch Seminar -Yonggang Jiang
— 1:00pm
Speaker:
YONGGANG JIANG
,
Max Planck Institute
https://yonggangjiang.github.io/
We present a parallel algorithm for computing (1+ ε) approximate mincost flow on an undirected graph with m edges, where capacities and costs are assigned to both edges and vertices. Our algorithm achieves m1+o(1) work and no(1) depth when ε > 1/polylog(m) making both the work and depth almost optimal, up to a subpolynomial factor.
Previous algorithms with m1+o(1) work required Ω(m) depth, even for special cases of mincost flow with only edge capacities or max flow with vertex capacities.
Our key technical contribution is the first construction of length-constrained flow shortcuts with (1+ ε) length slack, no(1) congestion slack, and no(1) step bound. This provides a strict generalization of the influential concept of (n{o(1),ε)-hopsets [Cohen94], allowing for additional control over congestion. Previous length-constrained flow shortcuts [HHLRS24] incur a large constant in the length slack, which would lead to a large approximation factor.
For More Information:
hfleisch@andrew.cmu.edu | gzli@andrew.cmu.edu