Cut Size Statistics of Graph Bisection Heuristics

Details Cut Size Statistics of Graph Bisection Heuristics Cut Size Statistics of Graph Bisection Heuristics

1998-04-03

arxiv.org/abs/cond-mat/9804027v1

SIAM Journal on Optimization, vol 10(1), p231-251 (1999)

Physics

Condensed Matter

Statistical Mechanics

17 pages, 5 figures, submitted to SIAM Journal on Optimization also available at http://ipnweb.in2p3.fr/~martino

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Cut Size Statistics of Graph Bisection Heuristics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cut Size Statistics of Graph Bisection Heuristics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cut Size Statistics of Graph Bisection Heuristics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-482079