Donald Bren School of Information and Computer Sciences

We consider optimization problems on complete graphs with edge weights drawn independently from a fixed distribution. We discuss several methods for analyzing these problems, including greedy methods, applications of Boole's inequality, and exploitation of relationships with results about random unweighted graphs. We illustrate these techniques in the case in which the edge weights are drawn from a normal distribution; in particular, we investigate the expected behavior of the minimum weight clique on k vertices. We describe the asymptotic behavior (in probability and/or almost surely) of the random variable which describes the optimum; we also discuss the asymptotic behavior of its mean. Next we demonstrate techniques by which we may determine an asymptotic description of the behavior of a greedy algorithm for this problem.