(I'd be interested to see an average-case running-time analysis of Simplex that yields O(n^2.332) additions/multiplications, where n is the number of variables.

(I'd be interested to see an average-case running-time analysis of Simplex that yields O(n^2.332) additions/multiplications, where n is the number of variables. Or even O(n^3). Because that's what's claimed here.) That's mostly correct. You end up with a system of equalities for _a subset_ of your points, which yields a single vertex. Ultimately with a linear program, you're trying to optimize an objective function, max w'x s.t. Ax <= b, x >= 0 (in canonical form). The x >= 0 constraint makes this nontrivial to translate from a linear equation Ax = b. If you magically knew the sign of each component of the solution, you'd be able to perform a simple variable substitution, but you generally don't, at least not without solving the system of equations. (And yes, you need that constraint, or else your LP is unbounded, and your solution ends up with a negative infinity in it.)