A Faster Parametric Search for the Integral Quickest Transshipment Problem

arXiv (Cornell University)

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.

Authors 4

1. Mariia Anapolska Aachen Combinatorial Optimization

   RWTH Aachen University

   Affiliation as printed

   Combinatorial Optimization, RWTH Aachen University, Germany

2. Dario van den Boom Aachen Combinatorial Optimization

   RWTH Aachen University

   Affiliation as printed

   Combinatorial Optimization, RWTH Aachen University, Germany

3. Christina Büsing Aachen Combinatorial Optimization

   RWTH Aachen University

   Affiliation as printed

   Combinatorial Optimization, RWTH Aachen University, Germany

4. Timo Gersing Aachen Combinatorial Optimization

   RWTH Aachen University

   Affiliation as printed

   Combinatorial Optimization, RWTH Aachen University, Germany