Non-adaptive Bellman-Ford: Yen's improvement is optimal
<|reference_start|>Non-adaptive Bellman-Ford: Yen's improvement is optimal: The Bellman-Ford algorithm for single-source shortest paths repeatedly updates tentative distances in an operation called relaxing an edge. In several important applications a non-adaptive (oblivious) implementation is preferred, which means fixing the entire sequence of relaxations upfront, independent of the edge-weights. In a dense graph on $n$ vertices, the algorithm in its standard form performs $(1 + o(1))n^3$ relaxations. An improvement by Yen from 1970 reduces the number of relaxations by a factor of two. We show that no further constant-factor improvements are possible, and every non-adaptive deterministic algorithm based on relaxations must perform $(\frac{1}{2} - o(1))n^3$ steps. This improves an earlier lower bound of Eppstein of $(\frac{1}{6} - o(1))n^3$. Given that a non-adaptive randomized variant of Bellman-Ford with at most $(\frac{1}{3} + o(1))n^3$ relaxations (with high probability) is known, our result implies a strict separation between deterministic and randomized strategies, answering an open question of Eppstein.<|reference_end|>
@article{hu2024non-adaptive,
    title={Non-adaptive Bellman-Ford: Yen's improvement is optimal},
    author={Jialu Hu, L'aszl'o Kozma},
    journal={arXiv preprint arXiv:2402.10343},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10343},
    primaryClass={cs.DS math.CO}
}