Our experiments are described in detail, and the results are presented in such a way as to reveal performance trends based on several variables. Sufficient trials are run to obtain 99% confidence intervals small enough to lead to a statistical ranking of the implementations for various circumstances.
The results for geometric graphs, which have become a frequently-used benchmark in the evaluation of partitioning algorithms, show that PO holds an advantage over the others.
In addition to the main test suite described above, comparisons of PO to more recent partitioning approaches are also given. We present the results of comparisons of PO with a parallelized implementation of Goemans' and Williamson's 0.878 approximation algorithm, a flow-based heuristic due to Lang and Rao, and the multilevel algorithm of Hendrickson and Leland.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-34.ps.gz
DIMACS Home Page