  We develop a multilevel algorithm for hypergraph partitioning that contracts
the vertices one at a time. Using several caching and lazy-evaluation
techniques during coarsening and refinement, we reduce the running time by up
to two-orders of magnitude compared to a naive $n$-level algorithm that would
be adequate for ordinary graph partitioning. The overall performance is even
better than the widely used hMetis hypergraph partitioner that uses a classical
multilevel algorithm with few levels. Aided by a portfolio-based approach to
initial partitioning and adaptive budgeting of imbalance within recursive
bipartitioning, we achieve very high quality. We assembled a large benchmark
set with 310 hypergraphs stemming from application areas such VLSI, SAT
solving, social networks, and scientific computing. We achieve significantly
smaller cuts than hMetis and PaToH, while being faster than hMetis.
Considerably larger improvements are observed for some instance classes like
social networks, for bipartitioning, and for partitions with an allowed
imbalance of 10%. The algorithm presented in this work forms the basis of our
hypergraph partitioning framework KaHyPar (Karlsruhe Hypergraph Partitioning).
