Abstract: We proposed a recursive dichotomy algorithm to solve the graph partitioning problem with vertex weight constraint. Firstly, the interior point method was used to solve the semidefinite programming relaxation model without vertex weight constraint. Secondly, the initial feasible solution satisfying the vertex weight constraint was obtained by hyperplane rounding algorithm. Thirdly, the heuristic algorithm was further designed to locally improve the initial feasible partition to obtain the optimal partition result. The experimental results show that the proposed algorithm can obtain the high quality solution to the multi-constraint graph partitioning problem in a short time.

Key words: graph partitioning, semidefinite programming, knapsack problem, combinatorial optimization