We propose a series of randomized greedy construction schemes for the hypergraph partitioning problem. While the final results are inferior 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 considered, 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 significant improvement of the average solution quality is achieved for comparable computation times.

Randomized Greedy Algorithms for the Hypergraph Partitioning Problem

RIZZI, ROMEO
1998-01-01

Abstract

We propose a series of randomized greedy construction schemes for the hypergraph partitioning problem. While the final results are inferior 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 considered, 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 significant improvement of the average solution quality is achieved for comparable computation times.
1998
hypergraph partitioning; clustering; greedy schemes; local search; tabu search; heuristics
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/435939
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact