Multi-way partitioning using bi-partition heuristics

The multi-way partition problem is very important in various applications. In this paper, we use analytical and experimental results to study the k-way partition problem. We introduce the concept of embedding graph for the the k-way partition problem. Based on this concept, we explain different scenarios of using a bi-partition heuristic to solve the k-way partition problem. If C denote the optimal cut cost for the k-way partition problem and the bi-partition heuristics we use are /spl delta/-approximation heuristics, we prove that the cut cost from the hierarchical approach has an approximate upper bound of /spl delta/C/spl middot/log k while the cut cost from the all-way bi-partition, or flat approach, has an upper bound of /spl delta/Ck. This is contrary to some claims made in the recent literature (and CAD tools designed based on it). Experimental results strongly support our theoretical analysis. Our results show that for large target graph, the hierarchical approach is about 77% better than the single-pass all-way bi-partition approach. The all-way bi-partition approach will perform better in a multipass set-up. However, the hierarchical approach is still on average 7.1% better in quality and 144 times faster than the multi-partition all-way bi-partition approach. The main conclusion of this paper is that, contradictary to what has been suggested in literature, hierarchical bi-partitioning is a more effective multi-way partitioning scheme.