News for hackers. Stuff that matters.
Re:First improvement of fundamental algorithm in 10 years by cdavidcash on Monday September 27, 2010 @06:46PM (#1733810)
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.

There are no comments on this comment yet.