An effective algorithm for multiway hypergraph partitioning

The problem of hypergraph partitioning has been around for more than a quarter of a century. Its early applications were centered on VLSI circuit design. In recent years, the application of hypergraph partitioning has been extended into the areas including data classifications, efficient storage of very large database and data mining. In this thesis, we propose an effective multiway hypergraph partitioning algorithm. We introduce the concept of net gain and embed it in the selection of cell moves. Unlike traditional FM-based iterative improvement algorithms in which the selection of the next cell to move is only based on its cell gain, our selection is based on both cell gains and net gains. To escape from local optima and to search broader solution space, we propose a new perturbation mechanism. These two strategies significantly enhance the solution quality produced by our algorithm. Based on our experimental justification, we also smoothly decrease the number of iterations from pass to pass to reduce the computational effort so that our algorithm can partition large circuits with reasonable run time. Compared with the recent multiway partitioning algorithms proposed by Dasdan and Aykanat, ours significantly outperforms theirs in term of solution quality (cutsize) and run time: the average improvements in terms of average cutsize over their PLM3 (Partitioning by Locked Moves) and PFM3 (Partitioning by Free Moves) are 47.64% and 36.76% with only 37.17% and 9.66% of their run time respectively