Optimal hypergraph partitioning

Warning The system is temporarily closed to updates for reporting purpose.

Usta, Baran (2018) Optimal hypergraph partitioning. [Thesis]

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://risc01.sabanciuniv.edu/record=b1817046 (Table of Contents)


Hypergraph partitioning into K parts has many applications in practice such as distributed algorithms and very large scale integrated circuit (VLSI) design. There are various tools proposed in the literature which can partition a given hypergraph very fast. However, since the problem is NP-Hard and the traditional approaches heavily use heuristics, these tools do not provide an optimal partition. There is limited research on partitioning hypergraphs optimally. In this thesis, we propose PHaraoh, a parallel hypergraph partitioner that can provide optimal partitions for many metrics used in the literature. Such a partitioner is important in practice since it enables us to evaluate the true performance of the existing tools. Furthermore, PHaraoh can be started with an initial partition. Thanks to that, even an optimal solution is not found within the given time limit, PHaraoh improves the cost of the provided initial partition. Experimental results on hypergraphs obtained from real-life matrices show that the quality of the partitions of existing tools can be improved significantly for most of the hypergraphs. In order to increase the speed up the search-space exploration, we experimented with both master-slave and workstealing parallelization. It also has been shown that the runtime of the algorithm highly depends on the order of the items in the branch and bound tree. In this study, we propose different ordering strategies which can offer great speed ups depending on the characteristics of the hypergraph

Item Type:Thesis
Uncontrolled Keywords:K-way hypergraph partitioning. -- Parallel branch and bound. -- Branch and bound reordering. -- Combinatorial algorithms. -- K parçalı hiperçizge parçalama. -- Dal ve sınır. -- Paralel hesaplama. -- Dal ve sınır sıralaması. -- Kombinatoryal algoritmalar
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
ID Code:36612
Deposited By:IC-Cataloging
Deposited On:06 Oct 2018 14:46
Last Modified:25 Mar 2019 17:30

Repository Staff Only: item control page