Random walks, totally unimodular matrices and a randomised dual simplex algorithm

Abstract: "We discuss the application of random walks to generating a random basis of a totally unimodular matrix and to solving a linear program with such a constraint matrix. We also derive polynomial upper bounds on the combinatorial diameter of an associated polyhedron."