3 ms·
Am I the only one suspicious of his claim "It will not do to say that it’s enough for the planners to approximate the optimal plan...This route is blocked."? I
by jeremysalwen 11y ago
Am I the only one suspicious of his claim "It will not do to say that it’s enough for the planners to approximate the optimal plan...This route is blocked."? It seems to me that in all my experience, computational complexity even for approximations rarely matches up with practical computation required. Computational complexity is worst case, doesn't understand the concept of "good enough for our application" when it's not mathematically defined.
For example, what's the computational complexity of training a deep neural network? Probably something pretty horrendous, even if you say it only has to be approximate within a factor of the optimal weights, and you allow it to fail some percent of the time, etc, etc. You could probably write an article about how training neural networks in the lifetime of the universe is impossible even in theory, if you defined "training a neural network" by starting out with the problem of finding the optimal weights, and then relaxing the requirements. But that entirely misses the point that training a neural network is not fundamentally about finding the optimal weights, but finding some weights which are good enough, which is measured in terms of real world performance in comparison to the alternatives.
Likewise, it seems like the discovery of the mathematics of linear optimization was mixed too strongly with the real-world problem it was trying to solve. The question is whether it is computationally feasible to outperform market based economies using this technique, and that's the only question that's really make-or-break it for the math side of things.
(Of course I may have misunderstood something, feel free to correct me)
- doctorpangloss 11y agoApproximation of integer programming problems (what the author is talking about more precisely) is actually pretty well studied. From Wikipedia: > NP-hard problems vary greatly in their approximability; some, such as the bin packing problem, can be approximated within any factor greater than 1 (such a family of approximation algorithms is often called a polynomial time approximation scheme or PTAS). Others are impossible to approximate within any constant, or even polynomial factor unless P = NP, such as the maximum clique problem. > NP-hard problems can often be expressed as integer programs (IP) and solved exactly in exponential time. Many approximation algorithms emerge from the linear programming relaxation of the integer program. It turns out that shortest paths finding (via Bellman-Ford), dynamic programming and linear programming are all interrelated. Figuring out how your linear program can be represented as some other problem, like shortest paths finding, directly yields to generic approximation.