Randomized greedy algorithms for the hypergraph partitioning problem

Abstract. We propose a series of randomized greedy construction schemes for the hypergraph partitioning problem. While the nal results are infe-rior to those obtained by recent multi-level methods, the advantages of our greedy schemes are their simplicity and low computational complexity. The best greedy algorithms considered obtain low cut values and large standard deviations of the results. Therefore, when independent repetitions are con-sidered, the quality of the best solution greatly improves and, in some cases, it is superior to the variable-depth Fiduccia-Mattheyses (FM) algorithm, for smaller CPU times. Furthermore, the algorithms can be used as building blocks in more complex schemes. For example, we successfully employ our greedy schemes to produce initial partitions for improvement-based heuristics. In particular, if FM is run starting from partitions generated by our greedy schemes, instead of random initial solutions, a signicant improvement of the average solution quality is achieved for comparable computation times. 1