A deterministic annealing approach to the graph partitioning problem

Abstract

The graph partitioning problem (GPP) has extensive applications in practice. However, due to its computational complexity of NP-completeness, it is very di±cult to solve to optimality with an exact algorithm in polynomial time. Hence one tends to ¯nd some heuristic methods to obtain a comparatively good approximate solution. In this thesis, after a brief introduction in Chapter 1 to the application of GPP in such ¯elds as VLSI design and parallel computing, we review its state-of-the-art algorithms in Chapter 2. In Chapter 3, we ¯rst address the equal-sized graph bipartitioning problem which is formulated as a linearly constrained optimization problem with binary variables. In order to solve this combinatorial optimization problem, a deterministic annealing approach (DAA) is proposed. DAA involves two steps: (1) Relax the binary variables to be continuous in a certain interval and introduce a logarithmic barrier function to handle the relaxed boundary constraints, from which a barrier problem results; (2) employ the Lagrangian multiplier method to generate a local minimum point of this barrier problem. Based on a feasible descent direction, the Lagrangian multiplier method is able to ¯nd a better solution in each step to the barrier problem with the property that lower and upper bounds on variables are always satis¯ed automatically if the step length is a number between zero and one. For a sequence of descending values of the barrier parameter with zero limit, DAA can be proved to converge to at least a local minimum point of the equal-sized graph bipartitioning problem if local minimum points are generated of the barrier problem with di®erent values of the barrier parameter. We then extend DAA to approximating solutions of unequal-sized graph bipartitioning problems and generic graph partitioning problems. Finally, to verify the e®ectiveness of DAA, numerical simulation is conducted in Chapter 4 based on randomly generated testing graphs, whose results reveal that DAA is better than other four state-of-the-art algorithms in terms of solution quality.

Date of Award	2 Oct 2009
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chuangyin DANG (Supervisor)