Faster Than Dijkstra? | Hacker News Reader

Faster Than Dijkstra?

systemsapproach.org

147 pointsdrbruced86 comments

The underlying argument this article seems to be making is that an appropriate algorithm for any given application isn't always the one with the most efficient asymptotic performance for sufficiently large n -- for a given application (in this case routing), we have data on typical values of n that appear in reality and we can choose an algorithm that offers good enough (or optimal) performance for n in that constrained range, as well as potentially having other benefits such being simpler to implement correctly in a short amount of engineering time.

This argument is very much in line with Mike Acton's data-driven design philosophy [1] -- understand the actual specific problem you need to solve, not the abstract general problem. Understand the statistical distribution of actual problem instances, they'll have parameters in some range. Understand the hardware you're building writing software for, understand its finite capacity & capability.

It's common that new algorithms or data-structures with superior asymptotic efficiency are less performant for smaller problem sizes vs simpler alternatives. As always, it depends on the specifics of any given application.

[1] see Mike's CppCon 2014 talk "Data-Oriented Design and C++" https://www.youtube.com/watch?v=rX0ItVEVjHc

I came to realize that logs don't matter. O(log(n)) and O(1) are effectively the same thing.

The reason is that real computers have memory, accessing memory takes time, and bigger n needs more memory, simply to store the bits that represent the number. Already, we have a factor of O(log(n)) here.

But also each bit of memory takes physical space, we live in a 3D world, so, best case, on average, the distance to a memory cell is proportional to the cube root of the amount of memory cells we will have to access. And since the speed of light is finite, it is also a cube root in time.

So "constant time" is actually cube root on a real computer. And I am generous by saying "real". Real real computers have plenty of stuff going on inside of them, so in practice, complexity analysis at the O(log(n)) level is meaningless without considering the hardware details.

Going from log(n) to log2/3(n) is just an exercise in mathematics, it may lead to practical applications, but by itself, it doesn't mean much for your software.

Most of this is very true, except for the one caveat I'll point out that a space complexity O(P(n)) for some function P implies at least a O(cubedroot(P(n))) time complexity, but many algorithms don't have high space complexity. If you have a constant space complexity this doesn't factor in to time complexity at all. Some examples would be exponentiation by squaring, miller-rabin primality testing, pollard-rho factorization, etc.

Of course if you include the log(n) bits required just to store n, then sure you can factor in the log of the cubed root of n in the time complexity, but that's just log(n) / 3, so the cubed root doesn't matter here either.

> Already, we have a factor of O(log(n)) here.

Doesn’t that mean that O(log(n)) is really O(log²(n))?

You have to define what n is.

It’s clear from the parent comment that the number of bits needed to represent the input is meant here.

>logs don't matter. O(log(n)) and O(1) are effectively the same thing.

ever heard of a hashtable? that's because O(c) is better than O(log(N)). if they were the same, you would only have heard of binary search.

Please explain to me how you can hash n distinct strings into O(n) buckets in O(1) time. Please note that this process needs to work as n goes to infinity.

Hash tables are O(log n) structures when you don't hand-wave away the "compute a hash" part. The thing is, search trees are far worse than that in practice and you aren't hand-waving away the "compare two elements" part. That's where the real speed savings come from.

What I think you are saying is that computing the hash needs to process the entire string, and the length of that string roughly corresponds to log n, therefore it's O(log n). Not sure I am entirely convinced by that reasoning, but let's roll with it for now.

Because if you apply it to binary search, you need to compare the strings at every step, and by that logic, each of these operations is O(log n), which means your binary search is now O(log^2 n).

I guess the crux is that we are still comparing apples to oranges (or multiplication operations to comparison operations), and at the end what probably makes hashing faster is that we are not branching.

Still I don't think it makes sense to think of both hash tables and binary search as O(log n).

Hash tables are indeed O(1) in theory while binary search is O(log(N)) in theory, no problem with that.

But in practice, accessing a physical memory cell is not O(1), it is O(cuberoot(N)).

For a binary search, you need O(log(N)) operation, but each operation (accessing a memory cell) is O(cuberoot(N')) where N' is the number of elements up to the level of the tree you are at, ending at N for the last iteration. So that's O(sum(0, log(N), cuberoot(N/exp(n))), which simplifies to O(cuberoot(N)), exactly the same!

In real practice, the choice of binary search vs hash table depends on considerations like cache behavior. Hybrid methods combining hash tables with hierarchical data structures are often used when N is large. But that's my point, you won't choose a hash table over a binary search because one is O(1) and the other is O(log(n)), you chose one over the other because of how it fits your hardware architecture.

Contrast with, say, O(n.log(n)) over O(n^2). When n is large, barring space-time tradeoffs, you should always pick the O(n.log(n)) algorithm, because the reduction in complexity will always beat any sane hardware considerations.

> understand the actual specific problem you need to solve, not the abstract general problem. Understand the statistical distribution of actual problem instances, they'll have parameters in some range. Understand the hardware you're building writing software for, understand its finite capacity & capability.

Very much in line with what James Coplien and colleagues described with "Commonality and Variability Analysis" and "Family-oriented Abstraction, Specification, and Translation" (FAST) for Software Engineering in the 90's. Coplien's PhD thesis titled Multi-Paradigm Design and book titled Multi-Paradigm Design for C++ is based on this approach.

Commonality and Variability in Software Engineering (pdf) - https://www.dre.vanderbilt.edu/~schmidt/PDF/Commonality_Vari...

Multi-Paradigm Design (pdf of PhD thesis) - https://tobeagile.com/wp-content/uploads/2011/12/CoplienThes...

All of Knuth's Art of Computer Programming covers this too.

Each time a discussion about sorting starts, I'm reminded of a "lively debate" I had with my boss/friend about the most optimal sorting approach. He claimed it's O(n) pointing to counting sort as an example. This didn't sit well with me. A sorting algorithm, I insisted, should be defined something like "a function taking an unsorted array of elements and returning a sorted one". But it seems there is no agreed upon definition and you can have something like counting sort where you get an array in O(n) but still need O(m) to get the index of a specific element. I argued that then the best sorting algorithm is the do-nothing algorithm. It returns the initial array in O(1), but needd O(m log m) to get you the index of an element (it uses merge sort to do it).

You reminded me of "Sleep Sort" [0]

[0] https://news.ycombinator.com/item?id=2657277

Don't know about if Sleep Sort even is a valid sorting algorithm? Is this even real?

it's real (in that it works) but obviously it's a programming joke rather than anything anyone would ever use in a real system.

counting sort is O(nW), where W is largest value

if you don't care about W or it is essentially constant - then it can be dropped

but it is an input parameter that will change execution time

W is the span or range.

It's O(n+W), not O(n*W).

> if you don't care about W or it is essentially constant - then it can be dropped

Also, every algorithm that ends in a real computer is bound to a constant time. That's still not a practical thing to do.

The simplification is correct but not correctly stated (even though colloquially it's common to state it that way). Technically it's when some component of the algorithm is dwarfed by another, then you can exclude it (i.e. O(n+W) =~ O(n) when W <<< n, O(mn) =~ O(n) when m <<< n etc). It's colloquially shortened to "when it's a constant" because generally it's constant regardless of program execution whereas the variable parts of the formula actually do change and thus the big-O analysis does still give you a correct lower bound on the performance.

TLDR: You're being unhelpfully pedantic.

"ordering" means arranging things in order by some metric.

"sorting" means assigning things into bins (which are usually ordered).

This is news to me. Source?

What do you do when you sort your washing?

"The children were sorted in to two lines by gender then ordered by height"

You might substitute "sorted by height" but its certainly not a correction. While "ordered into lines" would be an error.

The sorting office for a postal service.

That's because it's not true.

https://www.merriam-webster.com/dictionary/ordering

Order - transitive verb - 1. to put in order : arrange - "The books are ordered alphabetically by author."

noun - 4. b(1) the arrangement, organization, or sequence of objects or of events - "alphabetical/chronological/historical order" "listed the items in order of importance"

https://www.merriam-webster.com/dictionary/sorting

Sort - transitive verb - 1. to put in a certain place or rank according to characteristics - "sort the mail" "sorted the winners from the losers" "sorting the data alphabetically"

noun - 5. an instance of sorting - "a numeric sort of a data file"

I don't get how this disagrees with what GGP wrote.

https://dictionary.cambridge.org/dictionary/english/sort

to put a number of things in an order or to separate them into groups: Paper, plastic, and cans are sorted for recycling.

sort something into something I'm going to sort these old books into those to be kept and those to be thrown away.

sort something by something You can use the computer to sort the newspaper articles alphabetically, by date, or by subject.

sort (through) She found the ring while sorting (through) some clothes.

I can’t think of a single time I’ve needed a sorted list of only numbers. It’s always numbers and something else, like names or dates. Maybe for median calculations, but I don’t even use those that much either. Especially in telemetry, where mean is easy and median is not.

To be pedantic, median is cheaper than sorting. O(n) with a quicksort-like algorithm.

Also, if you're taking an average of floating point numbers, you might want to sort it first and add from smallest to largest, to better preserve precision

An aside, but I recently learned -- if one is willing to use a very modest amount of memory -- summing floating-point numbers with no loss of precision is effectively a solved problem with the XSUM algorithm.

https://glizen.com/radfordneal/ftp/xsum.pdf

That paper explains some useful optimisation details, but obviously since the floats are all (either infinity or) some multiple of a known tiny fraction (their smallest non-zero number), we can definitely sum them accurately.

Not if the ratio between the largest and smallest floats is very large (2^(2^n)) where n is the number of bits in the exponent.

I think you either haven't thought about this or you did your math wrong.

You need (2^e)+m+1 bits. That is more bits than would fit in the cheap machine integer type you just have lying around, but it's not that many in real terms.

Let's do a tiny one to see though first, the "half-precision" or f16 type, 5 bits of exponent, 10 bits of fraction, 1 sign bit. We need 43 bits. This will actually fit in the 64-bit signed integer type on a modern CPU.

Now lets try f64, the big daddy, 11 exponent, 52 fraction, 1 sign bit so total 2048 + 52 + 1 = 2101 bits. As I said it doesn't fit in our machine integer types but it's much smaller than a kilobyte of RAM.

Edited: I can't count, though it doesn't make a huge difference.

You also need some extra bits at the top so that it doesn't overflow (e.g., on an adversarial input filled with copies of the max finite value, followed by just as many copies of its negation, so that it sums to 0). The exact number will depend on the maximum input length, but for arrays stored in addressible memory it will add up to no more than 64 or so.

Thanks, you're right there for accumulating excess, I don't think you can actually get to 64 extra bits but sure, lets say 64 extra bits if you want a general purpose in memory algorithm, it's not cheap but we shouldn't be surprised it can be done.

That’s great for mean, but you don’t need to sort for mean.

If the primary key is the number, it still works (and dates are just numbers by the way) because you can sort a heterogenous dataset by a single numeric key pretty trivially.

But sorting by arbitrary strings like names can’t avoid comparison sort.

That data structure isn’t an array of numbers, it’s an array of pointers to objects.

> I can’t think of a single time I’ve needed a sorted list of only numbers.

Gosh. Let me try to convince you.

I use permutation arrays all the time: lists of indexes that can be used across multiple vectors.

This is much faster than the pattern of scanning rows, constructing tuples of (thingToSort . thingIWantInThatOrder) and making a custom sort function, and destructuring those tuples...

And really, not having to write custom sort functions is really really nice.

> Especially in telemetry, where mean is easy and median is not.

Funny. Yes median is obvious with a permutation array, and maybe mean is less so.

When your data is really big and not very variable, mean of x is roughly the same as the mean of any sufficient sample of x, and that sample can be meaningfully represented as a permutation array!

You can get such an array with reservoir sampling and some maths, and (depending on what you know of your data and variance) sometimes even simpler tricks.

That's kindof actually how the "faster than dijkstra" trick referred-to in the article works: Data sets with small variance has this same property that the min of x is roughly the same as the min of a sufficient sample of x (where the size of sufficient has to do with the variance). And so on.

Another big use-case in my code is trees: Apter trees have a flat memory layout which is convenient for permutation arrays which can simultaneously represent index, rotation, tombstones, and all sorts of other things you might need to do with a tree.

Give it a dig. There's good stuff in there.

You have a list of IDs, and want to make them compact for storage or transport - fast and simple way is to sort and delta encode.

Hmm. That’s fair, though I’d probably use set operations instead. What you find though is that for most other problems besides diffing, ID order is not chronological order, so you need to sort by a date stamp instead. But I’m typically letting the database do that, so I’m a consumer of sorted numbers, but not an implementor. Because what I sort is nearly always compound sorts. By field A, then field B and field C if those two still don’t cut it.

Usually when one talk about sorting, without specifying closer, one means comparison sort [1], which indeed has an average-case lower bound of O(n*log(n)). In more special cases all kinds of other runtimes are possible.

1: https://en.wikipedia.org/wiki/Comparison_sort

Obligatory mention of the linear time analog sorting algorithm known as the “spaghetti algorithm”.

https://en.wikipedia.org/wiki/Spaghetti_sort

https://every-algorithm.github.io/2023/11/25/spaghetti_sort....

The equivalent for positive link weight shortest paths is the “string algorithm” — build the network out of string and pull taut between the two knots/nodes, the resulting set of taut links is the shortest path.

Deja Vu.

I read this article a few days ago I'm sure, word-for-word, but it wasn't on this site in OP? It stood out because when it mentioned textbooks and said "including ours" I looked at the site and thought to myself "they do textbooks?".

This submission was made three days ago and bumped two hours ago: https://news.ycombinator.com/submitted?id=drbruced

> and thought to myself "they do textbooks?".

Indeed: https://systemsapproach.org/books-html/

If you are cheap on money, but you do have time, and like to get into networking, I can only highly recommend https://book.systemsapproach.org/

The link to https://book.systemsapproach.org/internetworking/routing.htm... is in the first paragraph.

Interestingly sorting is O(N) for a surprisingly large class of datatypes. Anything that behaves well with lexicographic sorting really.

Supposing one uses a 'trie' as a priority queue, the inserts and pops are effectively constant.

Only if you assume a finite alphabet and bounded length. Relax either and you're back to O(n log n) for a fully general solution. Examples of both: tuples and strings.

(There's also the problem of how you define your computational model. You can do better than O(n log n) in transdichotomous models. I'm assuming the hand-wavy, naive model the average algorithms class goes along with.)

In the most extreme case of this, you can use Counting Sort. Tangential to this, Spaghetti Sort makes me wonder about which parts of CS (especially the data structures, like arrays) are objective or just accidental.

The transdichotomous model looks interesting.

If we're taking the pure math view, complexity analysis is agnostic to this. Strictly speaking you'd have to define how your abstract machine works: O(n log n) is (again, strictly speaking) literally just a set of functions. In practice we usually hand-wave this away (not without problems: arithmetic taking time O(log n) and hash table lookups taking time O(1) are not consistent with each other!)

The unstated implication is that the theory tracks with real world behavior. This is more or less the case for simple problems: your O(n^2) algorithm won't scale, your database query without an index will take forever and so on, it's definitely a useful and high-signal way of thinking about computational problems.

Obviously modern hardware isn't much like a 70s machine and things like "all memory accesses are O(1)" are so wrong it's not even funny.

It's a pure thought experiment with no possible counterfactual, but I think if you tried to develop basic CS theory from a purely mathematical angle (e.g. consider a machine defined so and so with basic operations costing 1, let's run with this ball without caring much about the real world) you'd naturally end up with some (but not all) of the concepts we're used to. For example, arrays and buffers are very natural. We need more space than our basic unit of memory can accomodate, let's use several in a row. Pointers also follow very nicely, and with them structures like linked lists. Other stuff like B-trees and to some extent hash-tables and friends very much less so, they're definitely "imported" from real-world usage.

> Only if you assume a finite alphabet and bounded length

You can generally reduce the problem to a finite alphabet by taking the finite subset that actually appears in the input.

If you have an unbounded length then you can make sorting O(l n) where `l` is a bound on the lengths of your input. It's still linear in n, and also better than the O(l n logn) you would with traditional comparison based algorithms once you factor in the O(l) complexity of the comparison function for such elements.

> O(l n)

If you don’t have large numbers of repeats of each element, then l needs to scale like O(log n), so O(l * n) is at least O(n log n).

Fundamentally, what’s going on here is that switching between computation models can easily add and remove log factors.

> so O(l * n) is at least O(n).

I guess you mean "at least O(n*log(n))".

Indeed, and thanks. I edited it :)

I think you're making some assumptions on n that I'm not making. I'm considering it to be the number of elements to sort, not the size of the input.

Suppose you have n elements to sort and you don't have duplicates. Each element is a string of L fixed size symbols (bits, bytes, whatever). And suppose that there are at least n/10 unique elements. You may replace 10 with any other constant. This means that, as you add more elements, you are not just adding more duplicates of the same values.

In order to have n/10 unique elements, you need to be able to construct n/10 different strings, which means that L needs to be at least log_(base = how many distinct symbols you have)(n/10), which is O(log n). So you have L * n = O(n log n) symbols to write down, and even reading the input takes time O(n log n).

As a programmer, it's very very easy to think "64-bit integers can encode numbers up to 2^64, and 2^64 is HUUUUGE, so I'll imagine that my variables can store any integer". But asymptotic complexity is all about what happens when inputs get arbitrarily large, and your favorite computer's registers and memory cells cannot store arbitrarily large values, and you end up with extra factors of log n that you need to deal with.

P.S. For fun, you can try to extend the above analysis to the case where the number of unique elements is sublinear in the number of elements. The argument almost carries straight through if there are at least n^c unique elements for 0 < c < 1 (as the c turns into a constant factor when you take the log), but there's room to quibble: if the number of unique elements is sublinear in n, one might argue that one could write down a complete representation of the input and especially the sorted output in space that is sublinear in L * n. So then the problem would need to be defined a bit more carefully, for example by specifying the the input format is literally just a delimited list of the element values in input order.

> You can generally reduce the problem to a finite alphabet by taking the finite subset that actually appears in the input.

You can generally sort any array in constant time by taking that constant to be the time it takes to sort the array using bubble sort.

Both are true in practice, so not unreasonable. For graph weights that is, not sorting.

That said the finite alphabet and bounded length requirements can be softened a bit. Even for general sorting algorithms.

I mean, for the kind of lexicographic sotable data we're talking about you can basically pick a convenient alphabet size without cost.

And unbounded length is not that big an obstruction. Sure you are going to need O(n log(n)) comparisons. But you can't compare data of unbounded length in constant time anyway. In the end you end up taking an amount of time that is at least proportional to the amount of data, which is optimal up to a constant factor. And if you fiddle with radix sort enough you can get it within something similar.

Basic ASCII strings and tuples aren't that big an obstruction. Fractions are more complicated.

Really the O(n log(n)) for comparison based sorts and O(N) for radix sort mean something different. One is the number of comparisons to the number of elements, and the other closer to the number of operations per amount of data. Though that assumes O(1) swaps, which is technically incorrect for data that doesn't fit a 64 bit computer.

Should have a more conspicuous link to the Quanta article that it references if not the original. (It’s there, just not on the top.)

https://www.quantamagazine.org/new-method-is-the-fastest-way...

https://arxiv.org/abs/2504.17033

He links to those in the first two sentences. How is that not "on the top"?

Many years ago, as an undergrad, I had a conversation with a grad student friend about the Selection algorithm (which will find the kth largest item in an unsorted list in O(n) time). I loved it, but when I tested it in practice it was slower than just sorting and selecting well into the billions of elements.

My friend said "that may be true, but consider the philosophical implication: because that algorithm exists, we know it's possible to answer the question in O(n) time. We once didn't know that, and there was no guarantee that it was possible. We might still be able to find a better O(n) algorithm."

I feel the same way about this. Sure, this might not be faster than Dijkstra's in practice, but now we know it's possible to do that at all.

am I missing something?

this was a lot of words that sum up to "I heard that new algorithm exists but spent zero effort actually evaluating it"

No, I don't think you're missing anything. He never answered the title of the post ("Faster Than Dijkstra?"). Instead he went on a huge tangent about his experience writing software for routers and is dismissive of the algorithm because the router problem space he was working in did not deal with a node count high enough to warrant the need for a more complex algorithm. Dijkstra's algorithm is used for problem spaces with far higher number of nodes than he mentions... basically an article that talks about some kind of interesting things but doesn't say much about its central question.

What I'm missing is certainly what the hell the algorithm even is and what is its complexity. This guy just rambles about old switches.

> What I'm missing is certainly what the hell the algorithm even is and what is its complexity.

https://arxiv.org/pdf/2504.17033 - Linked from the second sentence of the submission, not hard to track down. And the complexity (by which I presume you mean algorithmic complexity) is stated in the submission and in the PDF linked by the submission and that I just shared with you.

I did eventually find that yes, after sifting through the rest of the useless links, the quantamagazine article that says jack shit, the link to the ACM symposium call for submissions (lmao). Like come on, why label that "underlying research"?

And all of that was wasted time since it seems that this just isn't at all applicable to A* heuristics the way Dijkstra's is. It's only an improvement in a very specific case.

Intriguing article. Sometimes practical issues override theoretical ones, and it would be interesting to see which one dominates in networking.

(side note: does anyone else get thrown off by the Epilogue font? It looks very wide in some cases and very narrow in others... makes me want to override it with Stylus if my employer hadn't blocked browser extensions for security reasons, which raises the question of why I am even reading the article on this computer....)

Even Knuth, in TAOP, acknowledges that using O(n) asymptotic behavior as a measure of performance is just a heuristic and not an absolute.

Cache-awareness and structure discovery are 2 important tools of the engineer to optimize practical problems.

If we wanted a reliable measure of the difficulty of a problem instance, it should rely on a function of O(K(n)) where K is the kolmogorov complexity of the input.

I can only recommend (for all Germans here) this video from "dorfuchs":

https://youtu.be/3ge-AywiFxs?si=TbcRsBNkzGhpOxQ4&t=842

(timestamped=) He shows a derivation that at best, a sorting algorithm can do is O(n log(n)) for n real positive numbers.

From who now?

Graph Theory and AI have been forever linked because it turns out the human brain is ridiculously good at finding a path through a graph that is somewhere in the neighborhood of 97% optimal, and we can do it in minutes while a computer would take weeks or until the heat death of the universe to do it better.

It's vexatious how good we are at it, and it's exactly the sort of problem that Science likes. We know it's true, but we can't reproduce it outside of the test subject(s). So it's a constant siren song to try to figure out how the fuck we do that and write a program that does it faster or more reliably.

Traveling Salesman was the last hard problem I picked up solely to stretch my brain and I probably understand the relationship between TSP and linear programming about as well as a Seahawks fan understands what it is to be a quarterback. I can see the bits and enjoy the results but fuck that looks intimidating.

>while a computer would take weeks or until the heat death of the universe to do it better.

I don't buy this, approximation algorithms are an entire field of CS, if you're OK with an approximate solution I'm sure computers could do that quickly as well.

Approximations are often good enough, and even annealing tended to give you a better answer if you were willing to wait. Exhaustive search is NP. But part of TSP is that once you have a good answer, you can backtrack on a larger number of bad ones. So there is value to doing both.

And for some geometries, Djikstra and friends give you bounds on what the shortest path can be, within a factor of two, so you can start to carve out the problem space even before you’ve found a decent one.

standard algorithms for single-source/single-dest pathfinding scale log-linearly in the size of the graph, so compared to other combinatorial optimisation problems, optimal pathfinding is incredibly easy for computers to do & scales pretty well to industrial-sized problems. computers can also do optimal pathfinding for problems that humans would not be able to solve easily (because the graphs don't easily embed in 2d or 3d, say, so we can't bring our vision systems to bear)

other combinatorial optimisation problems - like the traveling salesman you mention - are much harder than pathfinding to solve optimally or even approximately

I struggle to see the point. The paper in question doesn't claim to be practically faster or to want to "replace" Dijkstra, they are just saying "we got a better big-O" and I don't see any reason to doubt they're wrong about that.

It's actually common for algorithms with a lower asymptotic complexity to be worse in practice, a classic example is matrix multiplication.

Also please, please, can we stop with the "eww, math" reactions?

> The new approach claims order (m log^(2/3) n) which is clearly going to be less for large enough n. (I had to take a refresher course on log notation before I could even write that sentence with any confidence.)

I'm sure the author is just exaggerating, he's clearly very competent, but it's a sentence with the vibes of "I can't do 7x8 without a calculator."

The Quanta article on the paper was considerably more breathless in describing a fine piece of work in mathematics. The author here points out that one of the things that makes Dijkstra's result iconic is that it could be used practically in a straightforward way. As an engineer, beautiful mathematics is useless if I can't convert it to running code.

Actually there's a whole bunch of mathematics which I find useful as an engineer because it tells me that the perfection I have vaguely imagined I could reach for is literally not possible and so I shouldn't expend any effort on that.

e.g Two body gravity I can just do the math and get exact answers out. But for N> 2 bodies that doesn't work and it's not that I need to think a bit harder, maybe crack out some graduate textbooks to find a formula, if I did hopefully the grad books say "Three body problem generally not amenable to solution". I will need to do an approximation, exact answers are not available (except in a few edge cases).

> Actually there's a whole bunch of mathematics which I find useful as an engineer because it tells me that the perfection I have vaguely imagined I could reach for is literally not possible and so I shouldn't expend any effort on that

That's actually given as a reason to study NP-completeness in the classic 1979 book "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Garey & Johnson, which is one of the most cited references in computer science literature.

Chapter one starts with a fictional example. Say you have been trying to develop an algorithm at work that validates designs for new products. After much work you haven't found anything better than exhaustive search, which is too slow.

You don't want to tell your boss "I can't find an efficient algorithm. I guess I'm just too dumb".

What you'd like to do is prove that the problem is inherently intractable, so you could confidently tell your boss "I can't find an efficient algorithm, because no such algorithm is possible!".

Unfortunately, the authors note, proving intractability is also often very hard. Even the best theoreticians have been stymied trying to prove commonly encountered hard problems are intractable. That's where the book comes in:

> However, having read this book, you have discovered something almost as good. The theory of NP-completeness provides many straightforward techniques for proving that a given problem is “just as hard” as a large number of other problems that are widely recognized as being difficult and that have been confounding the experts for years.

Using the techniques from the book you prove the problem is NP-complete. Then you can go to your boss and announce "I can't find an efficient algorithm, but neither can all these famous people". The authors note that at the very least this informs your boss that it won't do any good to fire you and hire another algorithms expert. They go on:

> Of course, our own bosses would frown upon our writing this book if its sole purpose was to protect the jobs of algorithm designers. Indeed, discovering that a problem is NP-complete is usually just the beginning of work on that problem.

...

> However, the knowledge that it is NP-complete does provide valuable information about what lines of approach have the potential of being most productive. Certainly the search for an efficient, exact algorithm should be accorded low priority. It is now more appropriate to concentrate on other, less ambitious, approaches. For example, you might look for efficient algorithms that solve various special cases of the general problem. You might look for algorithms that, though not guaranteed to run quickly, seem likely to do so most of the time. Or you might even relax the problem somewhat, looking for a fast algorithm that merely finds designs that meet most of the component specifications. In short, the primary application of the theory of NP-completeness is to assist algorithm designers in directing their problem-solving efforts toward those approaches that have the greatest likelihood of leading to useful algorithms.

I read it as a musing on the folly of improvements that don’t deliver benefits within the practical bounds of actual problems. Which is a lesson seen everywhere in physical systems and manufacturing. Is it an amazing insight? No, but it’s a lesson that is relearned by everyone several times.

More important is that the new algorithm has a multiplicative factor in m (edges), so it's only efficient for extremely sparse graphs.

If m > n (log n)^{1/3}

Then this algorithm is slower.

for 1 Million nodes, if the average degree is >3.5, the new algorithm has worse complexity (ignoring unstated constant factors)

Yeah, just based on this article that really stood out. It seems to be for a different use-case than Djikstra’s. An average degree of 3.5 seems like an extremely practical a useful use-case in real life, I just don’t see any reason to put it and Djikstra’s against each-other in a head-to-head comparison.

"Any sufficiently sparse graph is indistinguishable from a linked list" comes to mind ;)

A linked list is sparse by the metric of minimum maximum degree (2).

A maximally sparse connected graph by mean (degree edge/node ratio) is any tree (mean degree ~ 1), not necessarily a linked list.

> I struggle to see the point. The paper in question doesn't claim to be practically faster...

I struggle to see the point of your comment. The blog post in question does not say that the paper in question claims to be faster in practice. It simply is examining if the new algorithm has any application in network routing; what is wrong with that?

Reply on news.ycombinator.com