Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Researchers achieve ‘absurdly fast’ algorithm for network flow

quantamagazine.org

Post reply on HN
Print view View original

61–70 of 80 posts

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#61

Post by lkozma »

mauricioc wrote: post #58
Jweb_Guru wrote: post #49

Earlier quoted context omitted.

I'm sorry, but I'm pretty sure you are wrong there. m^(log(log(m))/log(m)) = log(m), and log(log(m))/log(m) is certainly not o(1) since it's nondecreasing (and that's just a single logarithm). I'm pretty sure o(1) requires your slowdown over linear to be faster asymptotically than any iterated logarithm, (so faster than log(log(m)), log(log(log(m))), etc.), which is close enough to linear time that calling it "almost…

log(log(m))/log(m) tends to zero as m tends to infinity, which is what it means to be o(1). It is decreasing for m > e^e. Besides n^(1+o(1)), the other common definition for "almost linear" is precisely O(n log^k (n)) for some k, no matter how large.

Your first point is correct, but just to clarify your second point, these two definitions are not quite equivalent, as there is a world of functions growing more quickly than log^k(n) no matter how large constant k, but still within n^o(1).

For an example, consider 2^sqrt(log(n)).

This is a bit similar to something being faster than polynomial, but slower than exponential.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#62

Post by lkozma »

wenc wrote: post #29
doctorhandshake wrote: post #9

Not a comment in regard to this article in particular, but I love Quanta Magazine. Just the right amount of detail for a non-scientist and consistently fascinating subject matter.

I don't. Most Quanta articles have this pattern: they pepper the article with quotes from famous professors and only mention the authors in the middle of the page. I suppose one could argue this provides context and is a kind of attestation to the importance/relevance of the work. But I don't think this is right. To me, I want to know who the authors are in the first paragraph. They deserve the credit. The famous pro…

You are right in general, but when the quote is from someone on whose research the result builds in an important way (as it is the case here), I would say it is fair.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#64

Post by dchftcs »

jl2718 wrote: post #47

Is there an implementation and benchmark for this? Skimming, it appears to be built upon many theoretical results, any one of which could require impractical problem sizes or machine memory. In my head, the term ‘absurdly fast’ implies a computational result rather than theory. Also, I don’t see many echoes of the Spielman paper which seems to be the focus of the article, and is a lot more understandable in my opinio…

Years ago I came up with the first algorithm to solve a problem in a niche area in polynomial time. It uses some fairly contrived techniques; the power of the polynomial, if we really tried to estimate it, would probably have been >=10, or even >=20. But some time later another group of researchers expanded a technique used in the algorithm to help solve the problem in a much more practical manner.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#65

Post by plopilop »

tromp wrote: post #46
titanomachy wrote: post #20

Earlier quoted context omitted.

I've been out of school for a while, what does m^(1+o(1)) mean? Isn't any constant trivially in "o(1)"? So m^1000 is in this class? Or are they using it informally to mean "a very small number"?

It means m^(1+eps) for arbitrarily small positive constant epsilon. So you can make it run in time O(m^1.1) but also in time O(m^1.00000001), where the latter will presumably have a larger constant implied by the O(). The technical reason you can make eps arbitrarily small is that it represent a function of m that tends to 0 as m tends to infinity.

Mhh, while what you are saying is not wrong (though I'm not convinced about the constant thing, given everything is asymptotic), it's a bit imprecise.

A more exact formulation would be m^(1+o(1)) is equal to m^(1 + eps(m)) for some eps where eps(m) -> 0 for m -> infty

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#66

Post by cschmidt »

robertlagrant wrote: post #52

Great article. Nitpick: I don't know why they repeatedly talked about linear time being related to "the time it takes to write it down". Well, I sort of do, but I feel that it's a little misleading, as people unfamiliar with the term might think it's more closely linked to writing than it is.

I imagine they're trying to say you can't have a sub-linear approach, because it takes linear time to specify the graph (going over it once). So the time to "write it down" is the best you can possibly do (for an exact method).

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#67

Post by pfdietz »

themonteray wrote: post #21
titanomachy wrote: post #20

Earlier quoted context omitted.

I've been out of school for a while, what does m^(1+o(1)) mean? Isn't any constant trivially in "o(1)"? So m^1000 is in this class? Or are they using it informally to mean "a very small number"?

o(1) is "little O" notation, where for a function y = o(f), y(x) / f(x) --> 0 as x --> infinity. In other words, y goes to 0 faster than f. In this context, m^(1 + o(1)) means roughly that you converge to linear time for large m.

Or, rather, it grows more slowly than m^(1 + epsilon) for any fixed epsilon > 0.

The function m log m is m^(1 + o(1)) but it grows more quickly than linear.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#68

Post by pfdietz »

DeathArrow wrote: post #31

So basically they took a greedy algorithm that used a combinatorial approach and transformed it to use a calculus approach by inspiring from a related problem of "electrical flow through a network". I wonder if it isn't possible to do this for other greedy algorithms, or algorithms which are trying to find optimal solutions through heuristics.

There are classes of problems for which greedy algorithms are known to provide optimal solutions. An example is maximum matching on bipartite graphs. This is related to combinatorial structures called matroids (and an extension called greedoids.)

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

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#69

Post by DIARRHEA_xd »

amelius wrote: post #54
bainsfather wrote: post #42

Earlier quoted context omitted.

Can anyone recommend a 'friendly' overview of the 'calculus approach'? The paper linked in the article from 2003/2008 has been split up into 3 rather technical articles - I was hoping for something easier that just gave me a flavour of the method.

Isn't the Quanta article supposed to be the 'friendly' overview?

It's lacking. Their explanation for the greedy algo is great, less so for every other. By the end of the article, their 'explanations' degrade to speed analogies.

If I have the names right, your parent is looking for the derivation of "Optimal Power Flow", and its linearization "Linear/DC OPF".

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#70

Post by mauricioc »

lkozma wrote: post #61
mauricioc wrote: post #58

Earlier quoted context omitted.

log(log(m))/log(m) tends to zero as m tends to infinity, which is what it means to be o(1). It is decreasing for m > e^e. Besides n^(1+o(1)), the other common definition for "almost linear" is precisely O(n log^k (n)) for some k, no matter how large.

Your first point is correct, but just to clarify your second point, these two definitions are not quite equivalent, as there is a world of functions growing more quickly than log^k(n) no matter how large constant k, but still within n^o(1). For an example, consider 2^sqrt(log(n)). This is a bit similar to something being faster than polynomial, but slower than exponential.

Thanks for the clarification! I didn't mean to say the two definitions were equivalent, as indeed they aren't. Rephrasing my second point to (hopefully) eliminate the ambiguity: There are two non-equivalent popular definitions for "almost linear" or "nearly linear" (n^(1+o(1)) and O(n log^k(n)), and nevertheless classifying "n log^1000 n" as almost linear is uncontroversial in the sense that both of the common definitions do it.

(The second paragraph of my original message addressed a point made in the parent's second paragraph, which has since been edited out.)

Post reply on HN