No post body was provided.
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
21–30 of 44 posts
Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
#22Does anyone know if these algorithms are practical on real problems on real machines, or is the constant term large enough you would normally just use a more traditional algorithm for most work?
Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
#23I 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.
Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
#24Does anyone know if these algorithms are practical on real problems on real machines, or is the constant term large enough you would normally just use a more traditional algorithm for most work?
The constants are enormous enough that you'd never want to use these algorithms in practice - for now, at least. There's a key problem that uf resolved would allow quite efficient implementations of this family of algorithms even on the GPU, something that previously wasn't really possible for such graph algorithms.
Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
#25I 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, loo…
I 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?
Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
#26I 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, loo…
I 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?
I 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).
Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
#27Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
#28Earlier quoted context omitted.
I 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?
I 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…
At what point are we looking at the inter-relationships and commonalities among all practical implementations which share common input [groups, types, {trait}], etc...
Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
#29Earlier quoted context omitted.
It's so amusing how interviewers pose questions that took PhD students years to invent the answers to. Just say you want me to memorize some algorithms and their time+space complexities, and regurgitate them on command.
That’s not what I’m looking for in those kinds of interviews. For example, one of my fav problems has a Range Sum Query tree idea as the main solution. But I’m more than happy to lead any developer to the solution, they come away happy with new knowledge, I see how they respond to hints and think on a new problem. Always fun and heard a lot of direct thanks for that from interviewees.
Hmm, I just get a link to HackerRank of Codility in the first screening round. I can’t understate how insulting I find this
Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
#30Coming to a software engineering interview near you!
It's so amusing how interviewers pose questions that took PhD students years to invent the answers to. Just say you want me to memorize some algorithms and their time+space complexities, and regurgitate them on command.
> It's so amusing how interviewers pose questions that took PhD students years to invent the answers to.
That doesn't really mean anything without additional context... like what the questions you're talking about were, or what the positions were, or what you claimed about your background, approximately how long ago said PhDs were earned, or what the interviewers actually expected from you (which may not have been the final solution at all), or... etc.
So much of what we learn, use, and understand was developed by people far more talented than us. Literally everything from algebra to binary digital logic. It should be obvious that something can be orders of magnitude more difficult to come up with the first time, when you have nobody to learn it from, and when the rest of the world is far behind where the field is, than it might be to come up with it when the entire world has advanced and you've (presumably) been taught extremely relevant material & perspective in a nice and polished classroom setting. Now, obviously, it can also be just as difficult in the second case as in the first case for some problems too. It depends entirely on the problem and context.