Accession Number : ADA115804

Title :   Optimization Algorithms on Random Graphs,

Corporate Author : NORTH CAROLINA UNIV AT CHAPEL HILL INST OF STATISTICS

Personal Author(s) : Kelly,D G ; Welsh,D J A

PDF Url : ADA115804

Report Date : Apr 1982

Pagination or Media Count : 13

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.

Descriptors :   *Algorithms, *Points(Mathematics), *Simplex method, Optimization, Graphs, Probability distribution functions, Asymptotic series, Random variables, Problem solving

Subject Categories : Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE