Random walks,totally unimodular matrices,and a randomised dual simplex algorithm |
| |
| Authors: | Martin Dyer Alan Frieze |
| |
| Institution: | (1) School of Computer Studies, University of Leeds, LS2 9JT Leeds, UK;(2) Department of Mathematics, Carnegie-Mellon University, 15213-3890 Pittsburgh, PA, USA |
| |
| 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.Supported by NATO grant RG0088/89.Corresponding author. Supported by NSF grants CCR-8900112, CCR-9024935 and NATO grant RG0088/89. |
| |
| Keywords: | Random walks Totally unimodular matrices Uniform generation Linear programming Diameter of polytopes |
| 本文献已被 SpringerLink 等数据库收录！ |
|
