6 ms·

Negative-weight single-source shortest paths in near-linear time

163 points by Anon84 4y ago

gigatexal 4y ago
I really do need to up my maths game so I can take advantage of all these papers and their new and novel solutions to things like this. Otherwise I’ll have to wait until someone throws it into a library :(
- evouga 4y ago
  Well, this is a very interesting theoretical breakthrough, but it remains to be seen how it benchmarks in practice. The constant and log factors might be steep for practical inputs.
- bee_rider 4y ago
  They look to have distilled things down to a pair of Algorithms in pseudocode, if you want to take a swing at implementation-for-understanding.
- anigbrowl 4y ago
  https://pimbook.org https://pimbook.org is accessible, modular, and does a great job in advising how to read intimidating-looking equations and translate them to basic programming contexts.
  - gigatexal 4y ago
    Thank you! The sample looked like it would hold my hand enough to be helpful but not insult my intelligence so I bought the e-book for 21 USD. Thanks again!
dataflow 4y ago
What are some applications of this problem (SSSP with negative-weight edges)? This looks awesome but I'm not sure where I would want to use it.
- DropPanda 4y ago
  One application of negative weights in a cost graph could be energy consumption for battery electric vehicles. Downhill, regenerative breaking can result in a net increase of battery charge.
sitkack 4y ago
Can someone ELI12? How big of a deal is this for real world applications? Presentation by Aaron Bernstein (coauthor) on the paper https://www.youtube.com/watch?v=Bpw3yqWT_d0 https://www.youtube.com/watch?v=Bpw3yqWT_d0 Presentation by Danupon Nanongkai (coauthor) on the paper https://www.youtube.com/watch?v=awvBpvlbG1M https://www.youtube.com/watch?v=awvBpvlbG1M Implementation in Java https://github.com/nevingeorge/Negative-Weight-SSSP https://github.com/nevingeorge/Negative-Weight-SSSP
- hammock 4y ago
  This article helped me (I’m not a math guy at all, just a quick learner) https://algs4.cs.princeton.edu/44sp/ https://algs4.cs.princeton.edu/44sp/ Read the top section then the first answer in the Q&A at the bottom. Basically the problem is to find the least-cost (shortest) path across a graph of nodes from point a to point b, but the best algorithm we have (Djikstra’s) runs in exponential time in the worst case when there are some negative edge weights (see context below). This guy found an algorithm that runs must faster, in near-linear time. Context that is helpful is to think of edge weights not as distances, but as time or cost (this allows negative weights). Imagine a process workflow or something. Another helpful context that emerges from this is “negative cycle” which is an endless loop of negative weight edges (therefore asking an algorithm to find the “shortest” lowest weight path from one point to another that includes that cycle will fail). You can have negative weights without negative cycles though
  - ithinkso 4y ago
    > but the best algorithm we have (Djikstra’s) runs in exponential time in the worst case Dijkstra doesn't handle negative weights so in that case you can use Ford-Bellman. It's slower than Dijkstra but far from exponential - O(VE) or something like that.
    - hammock 4y ago
      > Dijkstra doesn't handle negative weights I took this straight from the Q&A I referenced in my link: Q. Does Dijkstra's algorithm work with negative weights? A. Yes and no. There are two shortest paths algorithms known as Dijkstra's algorithm, depending on whether a vertex can be enqueued on the priority queue more than once. When the weights are nonnegative, the two versions coincide (as no vertex will be enqueued more than once). The version implemented in DijkstraSP.java (which allows a vertex to be enqueued more than once) is correct in the presence of negative edge weights (but no negative cycles) but its running time is exponential in the worst case.
gregfjohnson 4y ago
How does this compare to the classic Bellman-Ford algorithm and subsequent improvements by Yen and Bannister&Eppstein?
- Sniffnoy 4y ago
  I mean, the runtimes are right there in the abstract; this is pretty easy to compare. Bellman-Ford takes time Theta(|V||E|), and as best I can tell the improvements you mention don't change that, they're just constant-factor improvements. As opposed to this algorithm being O(|E|*log(|V|)^8*log(W)), where W is the largest absolute value of a negative edge. The abstract of this paper even compare the runtime to the state of the art, and what it compares to isn't Bellman-Ford or the improvements you mention; there had already been asymptotic improvements on those.
  - AndrewKemendo 4y ago
    Your answer assumes someone knows big O natively unfortunately Despite the prevalence of the question, most people (like myself) would have to break out one of our old textbooks to tell. Do you have a reference measure that might help? For example: a process that would take 10ms under the following conditions [a,b,c] now takes 9ms?
    - Thorrez 4y ago
      Real world benchmarks and big O measure different things, so one is not a substitute for another. Real world benchmarks don't just measure the algorithm, they also measure the implementation. By comparing big O, you can compare algorithms directly instead of comparing implementations of the algorithms. Big O doesn't take into account constant factors, the time variability of CPU operations (e.g. cache hit vs cache miss), implementation details, or that all useful input sizes might be small. This means that even though an algorithm might have a better big O, it might actually be worse than other algorithms for practical size inputs. Creating an algorithm with a better big O is a mathematical breakthrough, but it's not proof that it's going to be practical in the foreseeable future. If you want to additionally prove that, you need real-world benchmarks. So real-world benchmarks would be useful here for some people. It might not be useful for the authors though if their goal is just to prove algorithmic superiority rather than real-world superiority. Creating a real-world benchmark also has the problem that existing implementations have likely been tuned with microoptimizations for years, and the new algorithm's implementation won't have been, leading to an unfair comparison. Your example of 10ms vs 9ms is such a small difference that microoptimizations would matter much more than it.
vsskanth 4y ago
Not very knowledgeable but are there any implications for path planning for self driving cars ?
- repsilat 4y ago
  For path finding heuristic methods give "sub-linear" time usually (if you have a pre-processed unchanging network with random access and amortize its construction over many queries). A-star is the old school one, but folks use fancier methods today. In a server farm linear time is too slow, basically. Interestingly, on a vehicle just doing Dijkstra's for within-city pathfinding is probably fine though if you've optimised the constant factors down. Likely no negative costs.
- throw827474737 4y ago
  None, very irrelevant and where it applies very minor problem vs all the others ;)
- extropy 4y ago
  For most use cases shortest path is super simple and fast problem on modern PCs. So might be useful on extra large synthetic networks. Neural nets?, Trading logs?, Image processing? Also negative weights are rare in real life applications. And def not in what you would consider normal path planning.
oh_sigh 4y ago
Is there an intuitive explanation for how a log^8 ends up in the algorithm? Why not log^4 or 16?
bertman 4y ago
Quanta article about the paper, discussion from 3 days ago: https://news.ycombinator.com/item?id=34439701 https://news.ycombinator.com/item?id=34439701
- deleted 4y ago
  [deleted]
rhelz 4y ago
If you want to interview for any job at an FPGA company, please read this paper first :-). I majorly blew an interview question which this paper would have helped me ace.
- jldugger 4y ago
  Interesting, I'm not sure I see the link. Is SSSP relevant in programming FPGAs optimally?
  - klyrs 4y ago
    Pathfinding is crucial in the process of compiling your hardware description into a circuit on the FPGA. If you're writing for an FPGA, you wouldn't necessarily need to know it. If you want to work on the compilers, it would be quite relevant.
xiphias2 4y ago
Another paper with no open source implementation :( I loved it that it’s possible (just like the min cost flow improvements), but it’s just too long for me to understand and implement it.
- krackers 4y ago
  It's always annoying that algorithm papers only ever include pseudocode. It wouldn't take much more effort to also throw in a python implementation. It also reminds me of cases where people found the presented pseudocode was subtly incorrect (although the idea of the algorithm still held).
lambo4bkfast 4y ago
From the paper: "Two textbook algorithms for SSSP are Bellman-Ford and Dijkstra’s algorithm. Dijkstra’s algorithm is near-linear time (O(m + n log n) time)" This is incorrect; Dijkstra's Algorithm using a binary priority queue has: O((m + n)log n) time
- cashweaver 4y ago
  I recall that the quoted time complexity is correct, assuming the queue is a Fibonacci heap. https://en.m.wikipedia.org/wiki/Dijkstra%27s_algorithm#CITEREFFredmanTarjan1984 https://en.m.wikipedia.org/wiki/Dijkstra%27s_algorithm#CITER...
  - lambo4bkfast 4y ago
    Ah yes you're correct. Fibonacci heap's aren't usually used in most applications of dijkstra's algorithm (such as road networks) though because trading an O(logn) heap.decrease_key operation for an O(1) heap.decrease_key operation, but getting a slower heap.delete_min operation (by a constant factor) isn't worth it. This is because there are much fewer heap.decrease_key operations on average than Dijkstra's worst case analysis suggests. The expected number of heap.decrease_key operations is not large enough to offset the loss in average runtime for the heap.delete_min operation.
    - cashweaver 4y ago
      I didn't know that! Thank you for elaborating.

163 points by Anon84 4y ago

I really do need to up my maths game so I can take advantage of all these papers and their new and novel solutions to things like this. Otherwise I’ll have to wait until someone throws it into a library :(

evouga 4y ago
Well, this is a very interesting theoretical breakthrough, but it remains to be seen how it benchmarks in practice. The constant and log factors might be steep for practical inputs.
bee_rider 4y ago
They look to have distilled things down to a pair of Algorithms in pseudocode, if you want to take a swing at implementation-for-understanding.
anigbrowl 4y ago
https://pimbook.org https://pimbook.org is accessible, modular, and does a great job in advising how to read intimidating-looking equations and translate them to basic programming contexts.
- gigatexal 4y ago
  Thank you! The sample looked like it would hold my hand enough to be helpful but not insult my intelligence so I bought the e-book for 21 USD. Thanks again!

dataflow 4y ago

What are some applications of this problem (SSSP with negative-weight edges)? This looks awesome but I'm not sure where I would want to use it.

DropPanda 4y ago
One application of negative weights in a cost graph could be energy consumption for battery electric vehicles. Downhill, regenerative breaking can result in a net increase of battery charge.

sitkack 4y ago

Can someone ELI12? How big of a deal is this for real world applications? Presentation by Aaron Bernstein (coauthor) on the paper https://www.youtube.com/watch?v=Bpw3yqWT_d0 https://www.youtube.com/watch?v=Bpw3yqWT_d0 Presentation by Danupon Nanongkai (coauthor) on the paper https://www.youtube.com/watch?v=awvBpvlbG1M https://www.youtube.com/watch?v=awvBpvlbG1M Implementation in Java https://github.com/nevingeorge/Negative-Weight-SSSP https://github.com/nevingeorge/Negative-Weight-SSSP

hammock 4y ago
This article helped me (I’m not a math guy at all, just a quick learner) https://algs4.cs.princeton.edu/44sp/ https://algs4.cs.princeton.edu/44sp/ Read the top section then the first answer in the Q&A at the bottom. Basically the problem is to find the least-cost (shortest) path across a graph of nodes from point a to point b, but the best algorithm we have (Djikstra’s) runs in exponential time in the worst case when there are some negative edge weights (see context below). This guy found an algorithm that runs must faster, in near-linear time. Context that is helpful is to think of edge weights not as distances, but as time or cost (this allows negative weights). Imagine a process workflow or something. Another helpful context that emerges from this is “negative cycle” which is an endless loop of negative weight edges (therefore asking an algorithm to find the “shortest” lowest weight path from one point to another that includes that cycle will fail). You can have negative weights without negative cycles though
- ithinkso 4y ago
  > but the best algorithm we have (Djikstra’s) runs in exponential time in the worst case Dijkstra doesn't handle negative weights so in that case you can use Ford-Bellman. It's slower than Dijkstra but far from exponential - O(VE) or something like that.
  - hammock 4y ago
    > Dijkstra doesn't handle negative weights I took this straight from the Q&A I referenced in my link: Q. Does Dijkstra's algorithm work with negative weights? A. Yes and no. There are two shortest paths algorithms known as Dijkstra's algorithm, depending on whether a vertex can be enqueued on the priority queue more than once. When the weights are nonnegative, the two versions coincide (as no vertex will be enqueued more than once). The version implemented in DijkstraSP.java (which allows a vertex to be enqueued more than once) is correct in the presence of negative edge weights (but no negative cycles) but its running time is exponential in the worst case.

gregfjohnson 4y ago

How does this compare to the classic Bellman-Ford algorithm and subsequent improvements by Yen and Bannister&Eppstein?

Sniffnoy 4y ago
I mean, the runtimes are right there in the abstract; this is pretty easy to compare. Bellman-Ford takes time Theta(|V||E|), and as best I can tell the improvements you mention don't change that, they're just constant-factor improvements. As opposed to this algorithm being O(|E|*log(|V|)^8*log(W)), where W is the largest absolute value of a negative edge. The abstract of this paper even compare the runtime to the state of the art, and what it compares to isn't Bellman-Ford or the improvements you mention; there had already been asymptotic improvements on those.
- AndrewKemendo 4y ago
  Your answer assumes someone knows big O natively unfortunately Despite the prevalence of the question, most people (like myself) would have to break out one of our old textbooks to tell. Do you have a reference measure that might help? For example: a process that would take 10ms under the following conditions [a,b,c] now takes 9ms?
  - Thorrez 4y ago
    Real world benchmarks and big O measure different things, so one is not a substitute for another. Real world benchmarks don't just measure the algorithm, they also measure the implementation. By comparing big O, you can compare algorithms directly instead of comparing implementations of the algorithms. Big O doesn't take into account constant factors, the time variability of CPU operations (e.g. cache hit vs cache miss), implementation details, or that all useful input sizes might be small. This means that even though an algorithm might have a better big O, it might actually be worse than other algorithms for practical size inputs. Creating an algorithm with a better big O is a mathematical breakthrough, but it's not proof that it's going to be practical in the foreseeable future. If you want to additionally prove that, you need real-world benchmarks. So real-world benchmarks would be useful here for some people. It might not be useful for the authors though if their goal is just to prove algorithmic superiority rather than real-world superiority. Creating a real-world benchmark also has the problem that existing implementations have likely been tuned with microoptimizations for years, and the new algorithm's implementation won't have been, leading to an unfair comparison. Your example of 10ms vs 9ms is such a small difference that microoptimizations would matter much more than it.

vsskanth 4y ago

Not very knowledgeable but are there any implications for path planning for self driving cars ?

repsilat 4y ago
For path finding heuristic methods give "sub-linear" time usually (if you have a pre-processed unchanging network with random access and amortize its construction over many queries). A-star is the old school one, but folks use fancier methods today. In a server farm linear time is too slow, basically. Interestingly, on a vehicle just doing Dijkstra's for within-city pathfinding is probably fine though if you've optimised the constant factors down. Likely no negative costs.
throw827474737 4y ago
None, very irrelevant and where it applies very minor problem vs all the others ;)
extropy 4y ago
For most use cases shortest path is super simple and fast problem on modern PCs. So might be useful on extra large synthetic networks. Neural nets?, Trading logs?, Image processing? Also negative weights are rare in real life applications. And def not in what you would consider normal path planning.

oh_sigh 4y ago

Is there an intuitive explanation for how a log^8 ends up in the algorithm? Why not log^4 or 16?

bertman 4y ago

Quanta article about the paper, discussion from 3 days ago: https://news.ycombinator.com/item?id=34439701 https://news.ycombinator.com/item?id=34439701

deleted 4y ago
[deleted]

rhelz 4y ago

If you want to interview for any job at an FPGA company, please read this paper first :-). I majorly blew an interview question which this paper would have helped me ace.

jldugger 4y ago
Interesting, I'm not sure I see the link. Is SSSP relevant in programming FPGAs optimally?
- klyrs 4y ago
  Pathfinding is crucial in the process of compiling your hardware description into a circuit on the FPGA. If you're writing for an FPGA, you wouldn't necessarily need to know it. If you want to work on the compilers, it would be quite relevant.

xiphias2 4y ago

Another paper with no open source implementation :( I loved it that it’s possible (just like the min cost flow improvements), but it’s just too long for me to understand and implement it.

krackers 4y ago
It's always annoying that algorithm papers only ever include pseudocode. It wouldn't take much more effort to also throw in a python implementation. It also reminds me of cases where people found the presented pseudocode was subtly incorrect (although the idea of the algorithm still held).

lambo4bkfast 4y ago

From the paper: "Two textbook algorithms for SSSP are Bellman-Ford and Dijkstra’s algorithm. Dijkstra’s algorithm is near-linear time (O(m + n log n) time)" This is incorrect; Dijkstra's Algorithm using a binary priority queue has: O((m + n)log n) time

cashweaver 4y ago
I recall that the quoted time complexity is correct, assuming the queue is a Fibonacci heap. https://en.m.wikipedia.org/wiki/Dijkstra%27s_algorithm#CITEREFFredmanTarjan1984 https://en.m.wikipedia.org/wiki/Dijkstra%27s_algorithm#CITER...
- lambo4bkfast 4y ago
  Ah yes you're correct. Fibonacci heap's aren't usually used in most applications of dijkstra's algorithm (such as road networks) though because trading an O(logn) heap.decrease_key operation for an O(1) heap.decrease_key operation, but getting a slower heap.delete_min operation (by a constant factor) isn't worth it. This is because there are much fewer heap.decrease_key operations on average than Dijkstra's worst case analysis suggests. The expected number of heap.decrease_key operations is not large enough to offset the loss in average runtime for the heap.delete_min operation.
  - cashweaver 4y ago
    I didn't know that! Thank you for elaborating.