Skip to main content
Open Access Publications from the University of California

Maximization problems on graphs with edge weights chosen from a normal distribution


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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View