2017/01/01 by Yaroslav Akhremtsev, Tobias Heuer, Peter Sanders +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Image and Video Retrieval Techniques #Algorithm #Algorithms and Data Compression #Computer science #Discrete mathematics #Hash function #Heuristics #Hypergraph #Local search (optimization) #Mathematics #Parallel computing #Theoretical computer science #VLSI and FPGA Design Techniques
paper · doi:10.1137/1.9781611974768.3
openalex publication_date 2017/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We develop a fast and high quality multilevel algorithm that directly partitions hypergraphs into k balanced blocks – without the detour over recursive bipartitioning. In particular, our algorithm efficiently implements the powerful FM local search heuristics for the complicated k-way case. This is important for objective functions which depend on the number of blocks connected by a hyperedge. We also remove several further bottlenecks in processing large hyperedges, develop a faster contraction algorithm, and a new adaptive stopping rule for local search. To further reduce the size of hyperedges, we develop a pin-sparsifier based on the min-hashing technique that clusters vertices with similar neighborhood. Extensive experiments indicate that our KaHyPar-partitioner compares favorably with the best previous systems. KaHyPar is faster than hMetis and computes better solutions. KaHyPar's results are considerably better than the (faster) PaToH partitioner.