TY - JOUR

T1 - Algorithms for graph partitioning problems by means of eigenspace relaxations

AU - Tu, Chih Chien

AU - Shieh, Ce Kuen

AU - Cheng, Hsuanjen

PY - 2000/5/16

Y1 - 2000/5/16

N2 - Graph partitioning problems are NP-hard problems and very important in VLSI design. We study relations among several eigenvalue bounds and algorithms for graph partitioning problems. Also, we design an algorithm for the problems which performs the following: first it computes the k largest eigenvalues of the affine symmetric matrix function to attain Donath-Hoffman bound; then it calculates a relaxed partition which is an array constant factor of an eigenspace associated with k eigenvalues; finally it generates an actual partition from the relaxed solution of a method similar to Boppana's algorithm. To compute optimal eigenvalue bounds, one needs to solve eigenvalue optimization problems which minimize the sum of the k largest eigenvalues of the nonsmooth functions. We use a subgradient method to compute the Donath-Hoffman eigenvalue bound. Numerical results indicate that although the Donath-Hoffman bound is not tight for graph partitioning problems, our algorithm can generate optimal partitions.

AB - Graph partitioning problems are NP-hard problems and very important in VLSI design. We study relations among several eigenvalue bounds and algorithms for graph partitioning problems. Also, we design an algorithm for the problems which performs the following: first it computes the k largest eigenvalues of the affine symmetric matrix function to attain Donath-Hoffman bound; then it calculates a relaxed partition which is an array constant factor of an eigenspace associated with k eigenvalues; finally it generates an actual partition from the relaxed solution of a method similar to Boppana's algorithm. To compute optimal eigenvalue bounds, one needs to solve eigenvalue optimization problems which minimize the sum of the k largest eigenvalues of the nonsmooth functions. We use a subgradient method to compute the Donath-Hoffman eigenvalue bound. Numerical results indicate that although the Donath-Hoffman bound is not tight for graph partitioning problems, our algorithm can generate optimal partitions.

UR - http://www.scopus.com/inward/record.url?scp=0033875237&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033875237&partnerID=8YFLogxK

U2 - 10.1016/S0377-2217(99)00060-0

DO - 10.1016/S0377-2217(99)00060-0

M3 - Article

AN - SCOPUS:0033875237

SN - 0377-2217

VL - 123

SP - 86

EP - 104

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 1

ER -