Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912319094652928 |
|---|---|
| author | Rao, Satish |
| author_facet | Rao, Satish |
| contents | A classical algorithm by Bellman and Ford from the 1950's computes shortest paths in weighted graphs on $n$ vertices and $m$ edges with possibly negative weights in $O(mn)$ time. Indeed, this algorithm is taught regularly in undergraduate Algorithms courses.
In 2023, after nearly 70 years, Fineman \cite{fineman2024single} developed an $\tilde{O}(m n^{8/9})$ expected time algorithm for this problem. Huang, Jin and Quanrud improved on Fineman's startling breakthrough by providing an $\tilde{O}(m n^{4/5} )$ time algorithm.
This paper builds on ideas from those results to produce an $\tilde{O}(m\sqrt{n})$ expected time algorithm. The simple observation that distances can be updated with respect to the reduced costs for a price function in linear time is key to the improvement. This almost immediately improves the previous work. To produce the final bound, this paper provides recursive versions of Fineman's structures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_22613 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers Rao, Satish Data Structures and Algorithms Computational Complexity A classical algorithm by Bellman and Ford from the 1950's computes shortest paths in weighted graphs on $n$ vertices and $m$ edges with possibly negative weights in $O(mn)$ time. Indeed, this algorithm is taught regularly in undergraduate Algorithms courses. In 2023, after nearly 70 years, Fineman \cite{fineman2024single} developed an $\tilde{O}(m n^{8/9})$ expected time algorithm for this problem. Huang, Jin and Quanrud improved on Fineman's startling breakthrough by providing an $\tilde{O}(m n^{4/5} )$ time algorithm. This paper builds on ideas from those results to produce an $\tilde{O}(m\sqrt{n})$ expected time algorithm. The simple observation that distances can be updated with respect to the reduced costs for a price function in linear time is key to the improvement. This almost immediately improves the previous work. To produce the final bound, this paper provides recursive versions of Fineman's structures. |
| title | Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2503.22613 |