This dissertation focuses on computing high-quality solutions for the NP-hard balanced hypergraph partitioning problem: Given a hypergraph and an integer $k$, partition its vertex set into $k$ disjoint blocks of bounded size, while minimizing an objective function over the hyperedges. Here, we consider the two most commonly used objectives: the cut-net metric and the connectivity metric.

Since the problem is computationally intractable, heuristics are used in practice - the most prominent being the three-phase multi-level paradigm: During coarsening, the hypergraph is successively contracted to obtain a hierarchy of smaller instances. ... mehr

Since the problem is computationally intractable, heuristics are used in practice - the most prominent being the three-phase multi-level paradigm: During coarsening, the hypergraph is successively contracted to obtain a hierarchy of smaller instances. ... mehr

This dissertation focuses on computing high-quality solutions for the NP-hard balanced hypergraph partitioning problem: Given a hypergraph and an integer $k$, partition its vertex set into $k$ disjoint blocks of bounded size, while minimizing an objective function over the hyperedges. Here, we consider the two most commonly used objectives: the cut-net metric and the connectivity metric.

Since the problem is computationally intractable, heuristics are used in practice -- the most prominent being the three-phase multi-level paradigm: During coarsening, the hypergraph is successively contracted to obtain a hierarchy of smaller instances. ... mehr

Since the problem is computationally intractable, heuristics are used in practice -- the most prominent being the three-phase multi-level paradigm: During coarsening, the hypergraph is successively contracted to obtain a hierarchy of smaller instances. ... mehr

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

Publikationstyp |
Hochschulschrift |

Publikationsdatum |
26.02.2020 |

Sprache |
Englisch |

Identifikator |
KITopen-ID: 1000105953 |

HGF-Programm |
46.12.02 (POF III, LK 01) Data Activities |

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

Umfang |
XI, 283 S. |

Art der Arbeit |
Dissertation |

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

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

Prüfungsdatum |
11.12.2019 |

Referent/Betreuer |
Prof. P. Sanders |

Externe Relationen |
Forschungsdaten/Software |

Schlagwörter |
hypergraph partitioning, algorithm engineering, graph partitioning |

Relationen in KITopen |

KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft

KITopen Landing Page