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 language | English |
|---|---|
| Pages (from-to) | 8-13 |
| Number of pages | 6 |
| Journal | Networks |
| Volume | 52 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1 Aug 2008 |
| Externally published | Yes |
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver