| Article ID: | iaor19961411 |
| Country: | Netherlands |
| Volume: | 64 |
| Issue: | 1 |
| Start Page Number: | 1 |
| End Page Number: | 16 |
| Publication Date: | Mar 1994 |
| Journal: | Mathematical Programming (Series A) |
| Authors: | Dyer Martin, Frieze Alan |
| Keywords: | programming: linear, statistics: distributions |
The authors 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. They also derive polynomial upper bounds on the combinatorial diameter of an associated polyhedron.