2026-07-23T21:50:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24581 2025-12-16T14:01:07Z ddc:004 open_access

A Faster Parametric Search for the Integral Quickest Transshipment Problem Anapolska, Mariia van den Boom, Dario Büsing, Christina Gersing, Timo Flow over time dynamic transshipment quickest transshipment parametric submodular functions efficient algorithms 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, however, no structural improvements on their algorithm itself have yet been proposed. Runtime improvements are limited to general progress on submodular function minimization (SFM), which is an integral part of Hoppe and Tardos' algorithm. In fact, SFM constitutes the main computational load of the algorithm, as the runtime is blown up by using it within Megiddo’s parametric search algorithm. We replace this part of Hoppe and Tardos' algorithm with a more efficient routine that solves only a linear number of SFM and, in contrast to previous techniques, exclusively uses minimum cost flow algorithms within Megiddo’s parametric search. Our approach improves the state-of-the-art runtime from 𝒪̃(m⁴ k^15) down to 𝒪̃(m²k⁵ + m⁴ k²), where k is the number of terminals and m is the number of arcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mariia Anapolska and Dario van den Boom and Christina Büsing and Timo Gersing 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.112 urn:nbn:de:0030-drops-245817 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.112 eng https://creativecommons.org/licenses/by/4.0/legalcode