Acceleration for Distributed Transshipment and Parallel Maximum Flow

Abstract

We combine several recent advancements to solve $(1+\epsilon )$-transshipment and $(1+\epsilon )$-maximum flow with a parallel algorithm with $\tilde{O}(1/\epsilon )$ depth and $\tilde{O}(m/\epsilon )$ work. We achieve this by developing and deploying suitable parallel linear cost approximators in conjunction with an accelerated continuous optimization framework known as the box-simplex game by Jambulapati et al. (ICALP 2022). A linear cost approximator is a linear operator that allows us to efficiently estimate the cost of the optimal solution to a given routing problem. Obtaining accelerated $\epsilon$ dependencies for both problems requires developing a stronger multicommodity cost approximator, one where cancellations between different commodities are disallowed. For maximum flow, we observe that a recent linear cost approximator due to Agarwal et al. (SODA 2024) can be augmented with additional parallel operations and achieve ${\epsilon }^{-1}$ dependency via the box-simplex game. For transshipment, we also construct a deterministic and distributed approximator. This yields a deterministic CONGEST algorithm that requires $\tilde{O}({\epsilon }^{-1}(D+\sqrt{n}))$ rounds on general networks of hop diameter $D$ and $\tilde{O}({\epsilon }^{-1}D)$ rounds on minor-free networks to compute a $(1+\epsilon )$-approximation.

v2: fixed typos