Optimization Algorithms on Random Graphs,
Abstract
We consider random graphs on vertices 0,1,2,...,n in which each edge, independent of the others, is present with probability p and absent with probability q=1-p. On such a graph we consider two different random walks starting with vertex n, moving at each step from a vertex to a lower-numbered neighbor, and stopping when they reach either vertex 0 or a sink, a vertex with no lower-numbered neighbor. These walks are simplified attempts to reproduce probabilistically the behavior of the simplex algorithm on linear programs. We derive some simple asymptotic results on the distribution of the number of sinks in a random graph, and also on the distributions of the numbers of steps needed by each of the two random walks.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1982
- Accession Number
- ADA115804
Entities
People
- D. G. Kelly
- D. J. A. Welsh
Organizations
- University of North Carolina at Chapel Hill