Article ID: | iaor19991952 |
Country: | United Kingdom |
Volume: | 25 |
Issue: | 7/8 |
Start Page Number: | 519 |
End Page Number: | 530 |
Publication Date: | Jul 1998 |
Journal: | Computers and Operations Research |
Authors: | Tu Chih-Chien, Cheng Hsuanjen |
Keywords: | interior point methods, semidefinite programming |
In this paper, we study the spectral methods for graph bisection problems and conclude certain numerical results. Spectral methods contain two topics: eigenvalue bounds for graph bisection width and bisection algorithms with eigenvector space. Two graph bisection problems are mainly investigated: finding the best bisection for the equal-size graph bisection problem and choosing the best bisection among a set of graph bisection problems of specified sizes. To compute the optimal eigenvalue bounds, one needs to solve the eigenvalue optimization problem which minimizes the largest eigenvalue of an affine symmetric matrix function. The eigenvalue optimization problems are convex but usually nonsmooth. Thus, we transform the eigenvalue optimization problems into the semidefinite programming problems. Then we apply primal–dual interior point methods to solve the semidefinite programming problems. Finally, we use an eigenvector corresponding to the largest eigenvalue, which has attained the optimal bound, to bisect the graph into two pieces of specified size. The running time of our algorithm for finding the best bisection among a set of graph bisection problems of specified sizes is