04/01/1997 09:00 AM
Computer Engineering
Although spectral partitioning has been an active area of research, there are still many limitations which prevent its widespread use. These limitations include the inability to work directly with a hypergraph model, great difficulty in specifying design constraints, and the inability to specify arbitrary cost functions. None of those limitations are present in the commonly-used Kernighan- Lin/Fiduccia-Mattheyses (KLFM) style iterative improvement heuristics. Our current work focuses on developing a new multi-way, hybrid spectral/iterative hypergraph partitioning algorithm which combines the strengths of spectral partitioners and iterative improvement algorithms to create a new class of partitioners. We show how spectral information (the eigenvectors of a graph) can be incorporated into an iterative partitioning framework. We use spectral information to generate initial partitions, influence the selection of iterative improvement moves, and break out of local minima which may trap KLFM improvement algorithms. Our 3-way and 4-way partitioning results are better than the best published results, demonstrating the effectiveness of our new hybrid method.
