Looking at the opening picture: is it allowed to fly a drone over busy traffic?
Researchers achieve ‘absurdly fast’ algorithm for network flow
51–60 of 80 posts
Re: Researchers achieve ‘absurdly fast’ algorithm for network flow
#52Great 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.
Re: Researchers achieve ‘absurdly fast’ algorithm for network flow
#53So 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.
Linear electrical networks have no maximum current, though.
Re: Researchers achieve ‘absurdly fast’ algorithm for network flow
#54So 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.
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?
Re: Researchers achieve ‘absurdly fast’ algorithm for network flow
#55Looking at the opening picture: is it allowed to fly a drone over busy traffic?
Depends on the country's laws, the pilot certifications, the drone in question, the airspace that intersection sits on, and sometimes on the land owner.
There will be combinations of these where it's allowed.
Re: Researchers achieve ‘absurdly fast’ algorithm for network flow
#56Not 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…
I also find Quanta articles rarely satisfactory with respect to the historical and social aspects of science (culture, ideas, experiments, interest...) but prioritizing explaining research and concepts over talking about people is a well justified editorial choice for a scientific magazine.
In this case there is a link to the article in the first paragraph and as the article discusses the whole history of maximum flow finding the new and exciting developments in the second half is quite reasonable.
Re: Researchers achieve ‘absurdly fast’ algorithm for network flow
#57Earlier quoted context omitted.
The o(1) here represents a decreasing function in m, such as 1/m. (Note: This is little o, not big o.) Therefore, for any k > 1: m^(1+o(1)) grows more slowly than m^k but faster than m
I'm trying to come up with an example to check my understanding. n (log n)^k for some constant k would qualify right?
Yes. (log n)/(n^epsilon) tends to zero for any positive epsilon, and so log n = n^(o(1)). The same holds for (log n)^k.
Re: Researchers achieve ‘absurdly fast’ algorithm for network flow
#58Earlier quoted context omitted.
The notation means that it must be faster than m^t for any t strictly greater than one. Basically, it means that you can have any number of log factors on the running time, so it could be m*log(m)^1000
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.
Re: Researchers achieve ‘absurdly fast’ algorithm for network flow
#59Earlier 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.
Oh, so it is. I retract my comment. In that case it seems like a pretty stupid designation to me.
Re: Researchers achieve ‘absurdly fast’ algorithm for network flow
#60Amazing
Are we gonna see a lot of derived papers, where someone picks any old paper that uses a flow algorithm to solve task X and then presents the new result, we can improve the runtime of solving task X with the new flow algorithm?