Balanced k-Way Partitioning for Weighted Graphs

Balanced k-way partitioning for a weighted graph is to divide the vertex set of the graph into k disjoint subsets, in order to minimize the difference of the sums of the vertex-weights between two subsets, together with minimizing the sum of the edge-weights, whose incident vertices belong to different subsets. This k-way partitioning problem is widely applied in the areas such as hardwaresoftware co-design, VLSI design, data partitioning, etc., and it has been proved to be NP-complete. An efficient heuristic algorithm is proposed to generate a good approximate k-way partition by maximizing the sum of the weights associated with the inner edges of the subsets, together with a relatively balanced partition. In detail, the proposed heuristic algorithm constructs a subset S by selecting a group of neighboring vertices with the highest gain from its candidate subset for inclusion S until the sum of vertex-weights of S meets the demand. Moreover, we customize an approach based on tabu search to refine the heuristic partition. Experimental results show that, the proposed algorithm works more efficiently for average solution than the state-of-the-art on 86%, 81% and 68% graphs among the public benchmark, for the cases k=2,4,8, respectively, with the improvement up to 60%.