带权图的均衡k划分

带权图的均衡k划分是把一个图的顶点集分成k个不相交的子集，使得任意2个子集中顶点的权值之和的差异达到极小，并且连接不同子集的边权之和也达到极小.这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域，它已被证明是NP完全问题.首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法.该算法在保证子集均衡的条件下，采用最大化同一子集内部边权之和的策略来构造每一个顶点子集；构建子集S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中，直到子集S的顶点权值之和满足要求.此外，采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化.实验结果表明，当k分别取值为2，4，8时所提算法分别在86%，81%，68%的基准图上求得的平均解优于当前最新算法求得的平均解；解的最大改进幅度可达60%以上.

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%.