Fast Algorithms for Hop-Constrained Flows and Moving Cuts

11/02/2021
by   Bernhard Haeupler, et al.
0

Hop-constrained flows and their duals, moving cuts, are two fundamental quantities in network optimization. Up to poly-logarithmic factors, they characterize how quickly a network can accomplish numerous distributed primitives. In this work, we give the first efficient algorithms for computing (1 ±ϵ)-optimal h-hop-constrained flows and moving cuts with high probability. Our algorithms take Õ(m ·poly(h)) sequential time, Õ(poly(h)) parallel time and Õ(poly(h)) distributed CONGEST time. We use these algorithms to efficiently compute hop-constrained cutmatches, an object at the heart of recent advances in expander decompositions.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset