Fast Algorithms for Min-Mean-Cycle via Connections to Optimal Transport

Min-Mean-Cycle is the problem of finding a cycle in a weighted directed graph with minimum mean weight. Classical applications in operations research, max-plus algebra, and computer science have motivated a long line of work on solving Min-Mean-Cycle efficiently. In this talk, I’ll identify an intimate connection between two problems which are traditionally studied separately: Min-Mean-Cycle and Optimal Transport. This connection leads to a fast, practical algorithm for approximating Min-Mean-Cycle based on Matrix Balancing. For graphs with polylogarithmic diameter, this algorithm runs in near-linear time and is memory-optimal.

Joint work with Pablo Parrilo