OTOH, simplex is very efficient already. Average-case complexity for random matrices is polynomial, and there are some interesting results that extend beyond that (see http://arxiv.org/abs/cs/0111050).