The balanced hypergraph partitioning problem (HGP) asks for a partition of the node set

of a hypergraph into $k$ blocks of roughly equal size, such that an objective function defined

on the hyperedges is minimized. In this work, we optimize the connectivity metric,

which is the most prominent objective function for HGP.

The hypergraph partitioning problem is NP-hard and there exists no constant factor approximation.

Thus, heuristic algorithms are used in practice with the multilevel scheme as

the most successful approach to solve the problem: First, the input hypergraph is coarsened to

obtain a hierarchy of successively smaller and structurally similar approximations.

The smallest hypergraph is then initially partitioned into $k$ blocks, and subsequently,

the contractions are reverted level-by-level, and, on each level, local search algorithms are used

to improve the partition (refinement phase).

In recent years, several new techniques were developed for sequential multilevel partitioning

that substantially improved solution quality at the cost of an increased running time.

These developments divide the landscape of existing partitioning algorithms into systems that either aim for

... mehr

of a hypergraph into $k$ blocks of roughly equal size, such that an objective function defined

on the hyperedges is minimized. In this work, we optimize the connectivity metric,

which is the most prominent objective function for HGP.

The hypergraph partitioning problem is NP-hard and there exists no constant factor approximation.

Thus, heuristic algorithms are used in practice with the multilevel scheme as

the most successful approach to solve the problem: First, the input hypergraph is coarsened to

obtain a hierarchy of successively smaller and structurally similar approximations.

The smallest hypergraph is then initially partitioned into $k$ blocks, and subsequently,

the contractions are reverted level-by-level, and, on each level, local search algorithms are used

to improve the partition (refinement phase).

In recent years, several new techniques were developed for sequential multilevel partitioning

that substantially improved solution quality at the cost of an increased running time.

These developments divide the landscape of existing partitioning algorithms into systems that either aim for

... mehr

Zugehörige Institution(en) am KIT |
Institut für Theoretische Informatik (ITI) |

Publikationstyp |
Hochschulschrift |

Publikationsdatum |
24.11.2022 |

Sprache |
Englisch |

Identifikator |
KITopen-ID: 1000152872 |

HGF-Programm |
46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups |

Verlag |
Karlsruher Institut für Technologie (KIT) |

Umfang |
xii, 242 S. |

Art der Arbeit |
Dissertation |

Fakultät |
Fakultät für Informatik (INFORMATIK) |

Institut |
Institut für Theoretische Informatik (ITI) |

Prüfungsdatum |
26.10.2022 |

Schlagwörter |
graph partitioning, hypergraph partitioning, shared-memory algorithms, algorithm engineering, multilevel algorithms, graph data structures, scalable algorithms |

Referent/Betreuer |
Sanders, Peter Çatalyürek, Ümit |

KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft

KITopen Landing Page