OPTIMIZATION BY ITERATIVE IMPROVEMENT - AN EXPERIMENTAL EVALUATION ON2-WAY PARTITIONING

Recently, Johnson et al, [4] presented an excellent comparison of simu lated annealing [6] and Kernighan-Lin [5] algorithms, However, their t est beds were limited to random and geometric graphs [4]. We present a complete evaluation by adding real circuitry into the test beds, A tw o-level partitioning algorithm called the primal-dual algorithm [13] i s also incorporated for comparison. We show that at least 500 runs are necessary to demonstrate the performance of the Fiduccia-Mattheyses a lgorithm, whereas traditional way of evaluation tends to underestimate . Nevertheless, our new results show that for two-way partitioning on real circuits, the primal-dual algorithm is, in general, a better choi ce than both the Fiduccia-Mattheyses algorithm and the simulated annea ling algorithm. This conclusion is more likely to hold when the primal -dual algorithm is switched to a simpler mode.