Detailansicht

Computing Quickest Minimum Cost Transshipments Efficiently | Prof. Martin Skutella, Technische Universität Berlin

Kurzbeschreibung: While the minimum cost quickest flow problem is NP-hard, the quickest minimum cost flow problem can be solved efficiently via a straightforward reduction to the quickest flow problem without costs. More generally, we show how the quickest minimum cost transshipment problem can be reduced to the efficiently solvable quickest transshipment problem. More than 25 years ago, Hoppe and Tardos presented the first (strongly) polynomial-time algorithm for the quickest transshipment problem. Their approach, as well as subsequently derived algorithms with strongly polynomial running time, are hardly practical as they rely on parametric submodular function minimization via Megiddo's method of parametric search. We present a considerably faster algorithm that instead employs a subtle extension of the discrete Newton method and improves the running times of previous algorithms by several orders of magnitude. This is joint work with Miriam Schlöter (ETH Zürich) and Khai Van Tran (TU Berlin).
Startdatum: 22.11.2022 - 16:00
Enddatum: 22.11.2022 - 18:00
Adresse: Cartesium | Rotunde
Organisator/Ansprechpartner: Prof. Dr. Nicole Megow,
Preis: 0€

While the minimum cost quickest flow problem is NP-hard, the quickest minimum cost flow problem
can be solved efficiently via a straightforward reduction to the quickest flow problem without
costs. More generally, we show how the quickest minimum cost transshipment problem can be reduced
to the efficiently solvable quickest transshipment problem. More than 25 years ago, Hoppe and
Tardos presented the first (strongly) polynomial-time algorithm for the quickest transshipment
problem. Their approach, as well as subsequently derived algorithms with strongly polynomial
running time, are hardly practical as they rely on parametric submodular function minimization
via Megiddo's method of parametric search. We present a considerably faster algorithm that
instead employs a subtle extension of the discrete Newton method and improves the running times
of previous algorithms by several orders of magnitude. This is joint work with Miriam Schlöter
(ETH Zürich) and Khai Van Tran (TU Berlin).