Donald Bren School of Information and Computer Sciences

We consider optimization problems on complete graphs with edge weights chosen from identical but independent normal distributions. We show some very general techniques for obtaining upper and lower bounds on the asymptotic behavior of these problems. Often, but not always, these bounds are equal, enabling us to state the asymptotic behavior of the maximum. Problems in which the bounds are tight include finding the optimum traveling salesman tour, finding a minimum cost spanning tree, and finding a heaviest clique on k vertices. We then discuss some greedy heuristic algorithms for these problems.