A Faster Parametric Search for the Integral Quickest Transshipment Problem

Abstract

Algorithms for computing fractional solutions to the quickest transshipment problem have been significantly improved since Hoppe and Tardos first solved the problem in strongly polynomial time. For integral solutions, runtime improvements are limited to general progress on submodular function minimization, which is an integral part of Hoppe and Tardos' algorithm. Yet, no structural improvements on their algorithm itself have been proposed. We replace two central subroutines in the algorithm with methods that require vastly fewer minimizations of submodular functions. This improves the state-of-the-art runtime from $\tilde{O}(m^4{k}^{15})$ down to $\tilde{O}(m^2{k}^5+m^4{k}^2)$, where $k$ is the number of terminals and $m$ is the number of arcs.