# Acceleration for Distributed Transshipment and Parallel Maximum Flow

Preprint · Christoph Grunau, Rasmus Kyng, Goran Zuzic

- Archive id: arxiv:2511.06581
- Published: 2025-11-09
- arXiv: https://arxiv.org/abs/2511.06581
- Source URL: https://arxiv.org/abs/2511.06581
- PDF: https://arxiv.org/pdf/2511.06581
- Provenance: arxiv

## Abstract

We combine several recent advancements to solve $(1+\\varepsilon)$-transshipment and $(1+\\varepsilon)$-maximum flow with a parallel algorithm with $\\tilde{O}(1/\\varepsilon)$ depth and $\\tilde{O}(m/\\varepsilon)$ 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 $\\varepsilon$ 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 $\\varepsilon^{-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}(\\varepsilon^{-1}(D + \\sqrt{n}))$ rounds on general networks of hop diameter $D$ and $\\tilde{O}(\\varepsilon^{-1}D)$ rounds on minor-free networks to compute a $(1+\\varepsilon)$-approximation.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.