{"ID":2844493,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.06581","arxiv_id":"2511.06581","title":"Acceleration for Distributed Transshipment and Parallel Maximum Flow","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.","short_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 w...","url_abs":"https://arxiv.org/abs/2511.06581","url_pdf":"https://arxiv.org/pdf/2511.06581v2","authors":"[\"Christoph Grunau\",\"Rasmus Kyng\",\"Goran Zuzic\"]","published":"2025-11-09T23:54:11Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}