Algorithms for graph partitioning problems by means of eigenspace relaxations

Chih Chien Tu, Ce-Kuen Shieh, Hsuanjen Cheng

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)86-104
Number of pages19
JournalEuropean Journal of Operational Research
Volume123
Issue number1
DOIs
Publication statusPublished - 2000 May 16

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Algorithms for graph partitioning problems by means of eigenspace relaxations'. Together they form a unique fingerprint.

Cite this