  This paper investigates and bounds the expected solution quality of
combinatorial optimization problems when feasible solutions are chosen at
random. Loose general bounds are discovered, as well as families of
combinatorial optimization problems for which random feasible solutions are
expected to be a constant factor of optimal. One implication of this result is
that, for graphical problems, if the average edge weight in a feasible solution
is sufficiently small, then any randomly chosen feasible solution to the
problem will be a constant factor of optimal. For example, under certain
well-defined circumstances, the expected constant of approximation of a
randomly chosen feasible solution to the Steiner network problem is bounded
above by 3. Empirical analysis supports these bounds and actually suggest that
they might be tightened.
