Path optimization for graph partitioning problems

This paper presents a new heuristic for graph partitioning called Path Opti mization (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 d escribed in detail, and the results are presented in such a way as to revea l performance trends based on several variables. Sufficient trials are run to obtain 99% confidence intervals small enough to lead to a statistical ra nking of the implementations for various circumstances. The results for geo metric graphs, which have become a frequently used benchmark in the evaluat ion of partitioning algorithms, show that PO holds an advantage over the ot hers. In addition to the main test suite described above, comparisons of PO to mo re recent partitioning approaches are also given. We present the results of comparisons of PO with a parallelized implementation of Goemans' and Willi amson's 0.878 approximation algorithm, a flow-based heuristic due to Lang a nd Rao, and the multilevel algorithm of Hendrickson and Leland. (C) 1999 El sevier Science B.V. All rights reserved.