Performance of the relaxation algorithm for maximum-cut problems

Kiichi Urahama, Hiroshi Nishiyuki

Research output: Contribution to journalArticlepeer-review


A relaxation algorithm is presented for solving a class of combinatorial optimization problems called set-partitioning tasks. The convergence property of the presented algorithm is investigated theoretically. A performance guarantee is derived theoretically for the present algorithm applied to an NP-hard example problem called the maximum-cut graph partitioning. The experimental examination of its performance manifests its superiority in computational speed to the conventional gradient method.

Original languageEnglish
Pages (from-to)375-384
Number of pages10
JournalJournal of Circuits, Systems and Computers
Issue number4
Publication statusPublished - Aug 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'Performance of the relaxation algorithm for maximum-cut problems'. Together they form a unique fingerprint.

Cite this