Project
IN-5
Efficient Minimization of Parametric Submodular Functions for Quickest Transshipments
Project Heads
Martin Skutella
Project Members
Khai Van Tran
Project Duration
01.01.2022 – 31.12.2022
Located at
TU Berlin
Description
We study the algorithmic complexity of parametric submodular function minimization in the context of the Quickest Transshipment Problem, a fundamental problem in the field of flows over time.
In a recent development, new tools for the Discrete Newton method and kernelization techniques for parametric submodular function minimizations were created in order to optimize the time horizon in the context of the Quickest Transshipment Problem[1]. The only known algorithm for Integral Quickest Transshipments is due to Hoppe and Tardos[2] and in this context a parametric submodular function minimization occurs as well. In this project, we aim to develop novel algorithms that find Integral Quickest Transshipments and whose worst-case running is faster than previously known approaches by orders of magnitude.
Project Webpages
https://www3.math.tu-berlin.de/coga/research/projects/parametric-submodular-functions-qtp/
Selected Publications
[1] M. Schlöter, M. Skutella and K. V. Tran. “A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method”. In: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2022.
[2] B. Hoppe and É. Tardos. “The Quickest Transshipment Problem”. In: Mathematics of Operations Research 25.1 (2000).
Selected Pictures
Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)
As Title in the above form please add a copyright.
And please give a short description of the picture and the context in the above textbox.
Don’t forget to press the “Save changes” button at the bottom of the box.
If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.