Speeding Up Bellman Ford via Minimum Violation Permutations

Silvio Lattanzi, Ola Svensson, Sergei Vassilvitskii
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:18584-18598, 2023.

Abstract

The Bellman-Ford algorithm is a basic primitive for computing single source shortest paths in graphs with negative weight edges. Its running time is governed by the order the algorithm examines vertices for iterative updates on the value of their shortest path. In this work we study this problem through the lens of ’Algorithms with predictions,’ and show how to leverage auxiliary information from similar instances to improve the running time. We do this by identifying the key problem of Minimum Violation Permutations, and give algorithms with strong approximation guarantees as well as formal lower bounds. We complement the theoretical analysis with an empirical evaluation, showing that this approach can lead to a significant speed up in practice.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-lattanzi23a, title = {Speeding Up {B}ellman Ford via Minimum Violation Permutations}, author = {Lattanzi, Silvio and Svensson, Ola and Vassilvitskii, Sergei}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {18584--18598}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/lattanzi23a/lattanzi23a.pdf}, url = {https://proceedings.mlr.press/v202/lattanzi23a.html}, abstract = {The Bellman-Ford algorithm is a basic primitive for computing single source shortest paths in graphs with negative weight edges. Its running time is governed by the order the algorithm examines vertices for iterative updates on the value of their shortest path. In this work we study this problem through the lens of ’Algorithms with predictions,’ and show how to leverage auxiliary information from similar instances to improve the running time. We do this by identifying the key problem of Minimum Violation Permutations, and give algorithms with strong approximation guarantees as well as formal lower bounds. We complement the theoretical analysis with an empirical evaluation, showing that this approach can lead to a significant speed up in practice.} }
Endnote
%0 Conference Paper %T Speeding Up Bellman Ford via Minimum Violation Permutations %A Silvio Lattanzi %A Ola Svensson %A Sergei Vassilvitskii %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-lattanzi23a %I PMLR %P 18584--18598 %U https://proceedings.mlr.press/v202/lattanzi23a.html %V 202 %X The Bellman-Ford algorithm is a basic primitive for computing single source shortest paths in graphs with negative weight edges. Its running time is governed by the order the algorithm examines vertices for iterative updates on the value of their shortest path. In this work we study this problem through the lens of ’Algorithms with predictions,’ and show how to leverage auxiliary information from similar instances to improve the running time. We do this by identifying the key problem of Minimum Violation Permutations, and give algorithms with strong approximation guarantees as well as formal lower bounds. We complement the theoretical analysis with an empirical evaluation, showing that this approach can lead to a significant speed up in practice.
APA
Lattanzi, S., Svensson, O. & Vassilvitskii, S.. (2023). Speeding Up Bellman Ford via Minimum Violation Permutations. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:18584-18598 Available from https://proceedings.mlr.press/v202/lattanzi23a.html.

Related Material