Skip to main navigation Skip to search Skip to main content

Spectral bounds for the maximum cut problem

  • CNRS SAMOVAR UMR 5157

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

Abstract

The maximum cut problem is a classical combinatorial optimization problem that is known to be NP-hard in general. In the present article, we provide some new lower and upper bounds that are based on the eigenvalues of the weight matrix with modified diagonal entries. Namely, we show that some upper bounds presented here are generally better than the SDP bound introduced by Goemans and Williamson, JACM 42 (1995), 1115-1145. We also discuss the complexity of computing these bounds and provide some preliminary computational results.

Original languageEnglish
Pages (from-to)8-13
Number of pages6
JournalNetworks
Volume52
Issue number1
DOIs
Publication statusPublished - 1 Aug 2008
Externally publishedYes

Keywords

  • Eigenvalues
  • Maximum cut
  • Relaxations

Fingerprint

Dive into the research topics of 'Spectral bounds for the maximum cut problem'. Together they form a unique fingerprint.

Cite this