Spectral methods for graph bisection problems

Spectral methods for graph bisection problems

0.00 Avg rating0 Votes
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: ,
Keywords: interior point methods, semidefinite programming
Abstract:

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 O(n3).

Reviews

Required fields are marked *. Your email address will not be published.