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

Wednesday, April 7, 2021 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Jason Altschuler



Zoom meeting id

942 5110 0835

Join Zoom meeting


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



Jason is a PhD student in LIDS, advised by Pablo Parrilo. His research interests are broadly in large-scale convex optimization, with a recent focus on fast, practical algorithms for Optimal Transport and related problems.