A Faster Parametric Search for the Integral Quickest Transshipment Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912796068806656 |
|---|---|
| author | Anapolska, Mariia Boom, Dario van den Büsing, Christina Gersing, Timo |
| author_facet | Anapolska, Mariia Boom, Dario van den Büsing, Christina Gersing, Timo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_12975 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Faster Parametric Search for the Integral Quickest Transshipment Problem Anapolska, Mariia Boom, Dario van den Büsing, Christina Gersing, Timo Data Structures and Algorithms Optimization and Control 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. |
| title | A Faster Parametric Search for the Integral Quickest Transshipment Problem |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2505.12975 |