  We investigate the statistical properties of cut sizes generated by heuristic
algorithms which solve approximately the graph bisection problem. On an
ensemble of sparse random graphs, we find empirically that the distribution of
the cut sizes found by ``local'' algorithms becomes peaked as the number of
vertices in the graphs becomes large. Evidence is given that this distribution
tends towards a Gaussian whose mean and variance scales linearly with the
number of vertices of the graphs. Given the distribution of cut sizes
associated with each heuristic, we provide a ranking procedure which takes into
account both the quality of the solutions and the speed of the algorithms. This
procedure is demonstrated for a selection of local graph bisection heuristics.
