0xDE on Nostr: Lower bounds for adaptive relaxation-based algorithms for single-source shortest ...

Lower bounds for adaptive relaxation-based algorithms for single-source shortest paths: https://arxiv.org/abs/2411.06546, by Sunny Atalig, Alexander Hickerson, Arrdya Srivastav, Tingting Zheng, and Marek Chrobak, to appear at ISAAC 2024.

This is part of a line of work including a paper of mine at WADS 2023 (see https://11011110.github.io/blog/2023/05/17/permutation-supersequences-shortest.html and https://arxiv.org/abs/2305.09230) where I proved that, among shortest-path algorithms that perform relaxation steps in a fixed order, depending on the graph but not on the results of previous steps, Bellman-Ford is within a constant factor of the optimal number of steps. In https://arxiv.org/abs/2402.10343, Jialu Hu and László Kozma eliminated the constant factor for deterministic algorithms on complete graphs, as a result showing that an older paper of mine, on a randomized version of Bellman–Ford (https://11011110.github.io/blog/2011/04/11/randomized-bellmanford.html and https://arxiv.org/abs/1111.5414) is strictly better than deterministic for this case. The new paper extends these results in a different direction, to algorithms whose order of operations depends (in a restricted way) on the results of previous operations, as you would want to do in any practical implementation of Bellman–Ford. For instance, once an edge has been relaxed, there's no point in doing it again until some other step has caused the distance to its starting vertex to improve.

If you want to see this at ISAAC, in Sydney, Australia, December 8–11, you need to preregister! Registration is open only until November 29, and will not be available at the conference. See https://sites.google.com/view/isaac2024/registration (via https://kamathematics.wordpress.com/2024/11/11/guest-post-isaac24-in-sydney-registration-deadline-soon/). And for the full list of ISAAC papers, see https://sites.google.com/view/isaac2024/list-of-accepted-papers