An experimental evaluation of local search heuristics for graph partitioning

A common problem that arises in many applications is to partition the vertices of a graph intok subsets, each containing a bounded number of vertices, such that the number of graph edges with endpoints in different subsets is minimized. This paper describes an empirical study of the performance of various local search heuristics for thisk-way graph partitioning problem. The heuristics examined are local optimization, simulated annealing, tabu search, and genetic algorithms. In addition, the hierarchical hybrid approach is introduced, in which the problem is recursively decomposed into small pieces, to which local search heuristics are then applied.