In math (well, in proofs) an answer must be "the" answer, a good enough answer is not good enough.
Those algorithms you mention provide reasonable answers, but they do not guarantee that the answer is the best answer.
Those algorithms you mention provide reasonable answers, but they do not guarantee that the answer is the best answer.
Simplex-type algorithms are typically used for these problems. These algorithms also have exponential time complexity in worst-case. In practice, well-designed simplex algorithms are of low-order-polynomial complexity. They terminate with an exact optimum.
This case, and others, are examples of situations where conventional complexity analysis fails to provide insight into real-world performance.
Last I knew, people were trying to analyze expected time complexity of certain (analysis-friendly) simplex algorithms under distributional constraints on the input structure matrices. But it's important to understand that this is mathematical back-filling to explain what is already known to hold in practice.
for worst case complexities it's often just a small region of the problem space that makes the bound large--but enumerating or cutting out those cases is tricky. you just don't see them on average because they are few (c.f., quicksort: O(n^2) worst case, O(n log n) average).
http://www.informs.org/Recognize-Excellence/Award-Recipients...
(expand out the "show more" button). Of course, there has been more progress since, but this summary is pretty good.
Interestingly they still use the simplex method repeatedly during the branch-and-bound solving process, because it only requires a little work to adjust at each step, whereas the methods with guaranteed polynomial worst case tend to take that polynomial time regardless of how "close" they start to the optimum. So, as you say, convential complexity analysis suggests that simplex would be an awful lot less useful than it is.
A probabilistic answer may be useful! But that's not the point of this proof.