Mathematical Programming
Volume 64, Numbers 1-3, 1-16, DOI: 10.1007/BF01582563

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

Martin Dyer and Alan Frieze

View Related Documents

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.

Key words  Random walks - Totally unimodular matrices - Uniform generation - Linear programming - Diameter of polytopes

Supported by NATO grant RG0088/89.
Corresponding author. Supported by NSF grants CCR-8900112, CCR-9024935 and NATO grant RG0088/89.

Fulltext Preview

Image of the first page of the fulltext document