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.
In this case the "greedy" algorithm was guaranteed to give the best possible flow in the network so this speedup applies to the optimal solution. I think in a lot of cases greedy algorithms are used when the alternative is an NP-hard problem like bin packing or TSP for which we might be looking at speeding up an already sub-optimal solution.
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.
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".
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.)
For a first exercise, forget Dijkstra and just solve a maze by doing Value Iteration, and plot the cost-to-go at each step.
Then consider that this function doesn't have to take a graph vertex or grid cell, but could instead be some continuous function on R^n.
The next step usually is to learn about the Linear Quadratic Regulator problem, where the cost-to-go is a quadratic, and you get to do an iteration of "Value Iteration" by updating the quadratic coefficients.
To connect to physics, see how you'd write the Action Integral in these terms.
From a layperson perspective maybe something like Fermat's Principle is what you are curious about. It also seems one can usually encode/send combinatorial problems into some other space or representation and decode them back into the discrete world. Generating functions and such.
> Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
> We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m^(1+o(1)) time. Our algorithm builds the flow through a sequence of m^(1+o(1)) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized m^o(1) time using a new dynamic graph data structure.
^ Our framework extends to algorithms running in m^(1+o(1)) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.
No. Any constant is in O(1), but not in o(1). Specifically, f=O(g) means f is (eventually) at most Cg for a certain C, but f=o(g) means f is (eventually) at most Cg for all C.
A useful, albeit not really rigorous, way to think about this is O is like ≤, while o is like <.
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.
I wish we could all collectively agree that using = for the o/O/etc. notations is stupid and stop this. These are sets of functions. f is not equal to the set, it is an element of the set and we already have a well defined notation for that: f ∈ o(...). So use that or use the LateX f \in o(...) if you want to restrict yourself to ASCII. Using = only serves to confuse.
(some descriptive linguistics) People often think of "=" as "is", when "is" can convey both equality and possession of an attribute. IIRC there was an article about how American kids think "=" means "the answer is" because they first encountered it with equations like 5+5=10. I've also seen people write 2x+5=10 = 2.5, meaning "the answer to the problem 2x+5=10 is 2.5"
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 linear" seems quite accurate!
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.)
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.
The best known algorithms, say relabel-to-front, is O(m^1.5) and the paper proposes an algorithm which is O(m^(1+o(1)). Here, 1.5 is fixed but 1+o(1) can be anywhere between 1 and 2 based on your luck, and should be 1.5 on an average over variety of inputs. Still no free lunch.
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 opinion.
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.
From TFA it appears this is not practical yet, maybe in the future:
> For now, it’s primarily a theoretical advance, since the speed improvements kick in only for networks that are far larger than the ones we encounter in the real world, for which maximum flow problems can already be solved fairly quickly (at least, if they don’t involve minimizing costs). But pieces of the new algorithm might see practical use within a year, predicted Richard Peng of the University of Waterloo in Canada, one of the algorithm’s six creators. And in the coming years, researchers said, computer scientists will likely find ways to make it more practical and perhaps even slightly faster.
I highly recommend Francis Spufford’s excellent Red Plenty, a very unusual book that combines soviet economics and computer science into a fictional narrative that centers upon this and other related problems.
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).
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?
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.
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 professor quotes should come later.
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.
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.
I'd agree with you ~1 year ago but I think a lot of their articles now tend to water-down lots of complex subjects in rigorous math papers. Still remains one of my favorite websites.
i think they have to water it down so much because hardly anyone would understand the math, even people who consider themselves good at math or have degrees in STEM..it's just so advanced even relative to that .
I think this is probably right. They are among the few to even attempt it.
As someone who loves math but who only knows a little, I find the articles manage to convey the broad ideas quite well. What it is, why it matters. I could stand more detail, but I guess many others couldn't.
Yeah this is me. No advanced STEM background so just barely hanging on by a thread. I enjoy being immersed in topics I don’t understand but I get more out of it with a little something to hang on to.
