Iterative partitioning with varying node weights

The balanced partitioning problem divides the nodes of a [hyper]graph into groups of approximately equal weight (i.e., satisfying balance constraints) while minimizing the number of[hyper]edges that are cut (i.e., adjacent to nodes in different groups). Classic iterative algorithms use the pass para digm [24] in performing single-node moves [16, 13] to improve the initial s olution. To satisfy particular balance constraints, it is usual to require that intermediate solutions satisfy the constraints. Hence, many possible m oves are rejected. Hypergraph partitioning heuristics have been traditionally proposed for and evaluated on hypergraphs with unit node weights only. Nevertheless, many r eal-world applications entail varying node weights, e.g., VLSI circuit part itioning where node weight typically represents cell area. Even when multil evel partitioning [3] is performed on unit-node-weight hypergraphs, interme diate clustered hypergraphs have varying node weights. Nothing prevents the use of conventional move-based heuristics when node weights vary, but thei r performance deteriorates, as shown by our analysis of partitioning result s in [1]. We describe two effects that cause this deterioration and propose simple mo difications of well-known algorithms to address them. Our baseline implemen tations achieve dramatic improvements over previously reported results (by factors of up to 25); explicitly addressing the described harmful effects p rovides further improvement. Overall results are superior to those of the P ROP-REXest algorithm reported in [14], which addresses similar problems.