3 ms·
I spent some (too many) months looking into this domain so I can maybe give some context. The astonishing improvement here is that we can compute exact flows i
by _hl_ 4y ago
I spent some (too many) months looking into this domain so I can maybe give some context.
The astonishing improvement here is that we can compute exact flows in almost-linear time. Previous algorithms for computing almost-optimal flows in almost-linear time have been known for some time, and hence it was expected that someone would eventually find an algorithm that finds optimal flows in almost-linear time. Well, looks like it's finally here!
I've only skimmed the paper but it seems to me that the authors draw on a set of techniques established for the almost-optimal case. These come with rather enormous constants, so it is unlikely that there will be a practical implementation of this algorithm any time soon.
- samstave 4y agoI am going to ask a question from a very naive POV, 5 yo: ELI5 the following please ; --- Given that "enormous constants" are required (i.e. huge lee-way) in the source of inputs (if thats worded correctly), Would it be perceivable, that in future, we may feed such zygote algorithms to some other AI/ML/Algo/Whatever, such that it churns through implementation scenarios quickly to refine it to a practical tool?
- qsort 4y agoI don't think the problem is that we can't develop a practical implementation, it's that the constant being hidden by the asymptotic notation is inherently huge, making the algorithm impractical given the input sizes we are interested in. There are a lot of problems where this shows up, notably testing primality (we can do that in poly time but it's O(n^6) or something iirc) and matrix multiplication (Strassen's algo).
- samstave 4y agoAt what point are we looking at the inter-relationships and commonalities among all practical implementations which share common input [groups, types, {trait}], etc...