Iterative Partitioning with Varying Node Weights

[摘要] The balanced partitioning problem divides the nodes of a [hyper]graph into groups ofapproximately equal weight (i.e., satisfying balance constraints) while minimizing thenumber of [hyper]edges that are cut (i.e., adjacent to nodes in different groups). Classiciterative algorithms use thepassparadigm [24] in performing single-node moves [16, 13]to improve the initial solution. To satisfy particular balance constraints, it is usual torequire that intermediate solutions satisfy the constraints. Hence, many possible movesare rejected.Hypergraph partitioning heuristics have been traditionally proposed for andevaluated on hypergraphs withunitnode weights only. Nevertheless, many real-worldapplications entail varying node weights,e.g., VLSI circuit partitioningwhere nodeweight typically represents cell area. Even whenmultilevelpartitioning [3] is performedon unit-node-weight hypergraphs, intermediate clustered hypergraphs have varyingnode weights. Nothing prevents the use of conventional move-based heuristics whennode weights vary, but their performance deteriorates, as shown by our analysis ofpartitioning results in [1].We describe two effects that cause this deterioration and propose simplemodifications of well-known algorithms to address them. Our baseline implementationsachieve dramatic improvements over previously reported results (by factors of up to 25);explicitly addressing the described harmful effects provides further improvement.Overall results are superior to those of the PROP-REXestalgorithm reported in [14],which addresses similar problems.

[学科分类] 电子、光学、磁材料