Path optimization for graph partitioning problems

This paper presents a new heuristic for graph partitioning called Path Optimization (PO), and the results of an extensive set of empirical comparisons of the new algorithm with two very well-known algorithms for partitioning: the Kernighan-Lin algorithm and simulated annealing. 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. (C) 1999 Elsevier Science B.V. All rights reserved.