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

First improvement of fundamental algorithm in 10 years

web.mit.edu

Post reply on HN
Print view View original

21–30 of 42 posts

Re: First improvement of fundamental algorithm in 10 years

#21

Post by jsolson »

kwantam wrote: post #20

This sounds cool, but how is this not a solution that's already been considered? It seems intuitively obvious to me that you can use a circuit simulator to solve this problem pretty quickly by assigning conductances to the edges of the graph. Modern circuit simulators are pretty good at converging on a solution in the presence of strong nonlinearities, so in principle you could even have edges that are more than simp…

> This sounds cool, but how is this not a solution that's already been considered? … I have a CS degree

Well… did you think of it?

Re: First improvement of fundamental algorithm in 10 years

#22

Post by danger »

schumitsch wrote: post #18
danger wrote: post #7

Earlier quoted context omitted.

The method sounds very interesting, but the title seems to overstate the work a bit. This is an approximation algorithm, meaning that it's an improvement on an _approximate_variant_of_ a fundamental problem, right?

I think the title is appropriate. The approximate solution is the interesting one, as the exact solution is believed to be intractable.

I don't think that's true. See, for example, Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching (Karger-Levine, 1997): http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.3...

Re: First improvement of fundamental algorithm in 10 years

#23

Post by jedbrown »

Groxx wrote: post #8

Very little info, but I'd argue that the parallel qualities of the new algorithm are at least of similar importance to the improvement in complexity. Old speed: (N + L)^(3/2) New speed: (N + L)^(4/3). (n=nodes, l=links) > For a network like the Internet, which has hundreds of billions of nodes, the new algorithm could solve the max-flow problem hundreds of times faster than its predecessor. Granted, it's massively us…

throw the sucker at a video card, and watch it finish thousands of times faster on cheaper hardware

This is nonsense even for dense operations. But this matrix is sparse, in which case GPUs are within a modest factor (2-5 or so depending on the matrix, whether you use multiple cores on the CPU, and whether you ask NVidia or Intel). And if the algorithm does not expose a lot of concurrency (as with most multiplicative algorithms), the GPU can be much slower than a CPU.

Re: First improvement of fundamental algorithm in 10 years

#24

Post by cdavidcash »

btilly wrote: post #17
danger wrote: post #7

Earlier quoted context omitted.

The method sounds very interesting, but the title seems to overstate the work a bit. This is an approximation algorithm, meaning that it's an improvement on an _approximate_variant_of_ a fundamental problem, right?

If you're able to find a rapidly converging sequence of approximations, then in finite time you can approximate arbitrarily well. Given the realities of finite numerical precision, this can be exactly as useful as an exact solution. We'll know more tomorrow.

Sadly, "finite time" is not what we need - they are looking for approximations that will be much rougher than the imprecision of finite numerical precision, and they want the approximation algorithm to have a good provable run time.

In general, taking theoretical approximation algorithms and shrinking the approximation factor to below some threshold where you "tell the difference" is a dead end. For instance, this algorithm's running time has a poly^{1/\epsilon} factor, so you pay a huge cost for it. It is better to think \epsilon = 1/3 or so.

Re: First improvement of fundamental algorithm in 10 years

#25

Post by cdavidcash »

schumitsch wrote: post #18
danger wrote: post #7

Earlier quoted context omitted.

The method sounds very interesting, but the title seems to overstate the work a bit. This is an approximation algorithm, meaning that it's an improvement on an _approximate_variant_of_ a fundamental problem, right?

I think the title is appropriate. The approximate solution is the interesting one, as the exact solution is believed to be intractable.

This is absolutely not true. The wikipedia page for the max flow problem lists several (slower) poly-time algorithms for solving exact max flow. Most theory-101 classes cover at least Ford-Fulkerson.

Re: First improvement of fundamental algorithm in 10 years

#26

Post by [deleted] »

kwantam wrote: post #20

This sounds cool, but how is this not a solution that's already been considered? It seems intuitively obvious to me that you can use a circuit simulator to solve this problem pretty quickly by assigning conductances to the edges of the graph. Modern circuit simulators are pretty good at converging on a solution in the presence of strong nonlinearities, so in principle you could even have edges that are more than simp…

[deleted]

Re: First improvement of fundamental algorithm in 10 years

#27

Post by shadowmatter »

Actually, another case: Vladimir Yaroslavskiy recently came up with a dual-pivot quicksort method where the number of swaps is reduced from 1nln(n) to 0.8nln(n). Yes, he's only twiddling the constant factor, but the benchmarks have been promising, with some sorts being reduced to 25% to 50% of their previous running time. Josh Bloch, one of the shepherds of Java, took the time to implement it as the default sorting algorithm in Java 7 (whenever that gets released). More details at: http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs...

How timsort from Python stacks up, I don't know offhand. But that's a different beast instead of an improvement to a fundamental algorithm.

Re: First improvement of fundamental algorithm in 10 years

#28

Post by kenjackson »

jongraehl wrote: post #16

It's an approximate algorithm (nothing wrong with that). I'm confused at how they claim O(m^{4/3}) (m is the number of edges) when even initializing an explicit n by n matrix is O(n^2), unless they assume that the graph isn't sparse (m>=k*n^1.5). Or perhaps the matrix is sparsely represented.

On page 11 of the paper I reference above Spielman makes the following statement:

"The most obvious way that sparsification can accelerate the solution of linear equations is by replacing the problem of solving systems in dense matrices by the problem of solving systems in sparse matrices. Recall that the Conjugate Gradient, used as a direct solver, can solve systems in n-dimensional matrices with m non-zero entries in time O(mn). So, if we could find a graph H with O(n) nonzero entries that was even a 1-approximation of G, then we could quickly solve systems in LG by using the Preconditioned Conjugate Gradient with LH as the preconditioner, and solving the systems in LH by the Conjugate Gradient. Each solve in H would then take time O(n^2), and the number of iterations of the PCG required to get an ǫ-accurate solution would be O(log ǫ−1). So, the total complexity would be O((m + n^2) log ǫ−1)."

I'm not really sure how you get O(n) 1-approximations of G (or even really what a 1-approximation is yet, as I haven't really read the paper), but that seems to be the idea, I think.

Re: First improvement of fundamental algorithm in 10 years

#29

Post by [deleted] »

danger wrote: post #7
superjared wrote: post #3

Earlier quoted context omitted.

Kelner is set to give a talk about it tomorrow[1]. Anyone know if they create videos for these? [1]: http://www.csail.mit.edu/events/eventcalendar/calendar.php?s...

The method sounds very interesting, but the title seems to overstate the work a bit. This is an approximation algorithm, meaning that it's an improvement on an _approximate_variant_of_ a fundamental problem, right?

[deleted]

Re: First improvement of fundamental algorithm in 10 years

#30

Post by askar_yu »

T_S_ wrote: post #2

The article refers to the max flow problem. About all this article does is imply that the new method involves the adjacency matrix of the graph and provides little else in the way of details. A better article is needed, not this oversimplified press release.

yes, but the article tries to explain the achieved work to people unfamiliar with Graph Theory or CS; thus in very simple terms and with analogies, they even define what a graph is before proceeding... I guess that's what it meant to be, short and simple press release with a (I'm assuming) follow up with the algorithm itself.
Post reply on HN