Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning

DOI10.1137/14099098XzbMath1331.68297OpenAlexW2063665970MaRDI QIDQ3453578

Jose A. Soto

Publication date: 27 November 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/14099098x

zbMATH Keywords

approximation algorithmsspectral graph theoryspectral partitioningMax-Cut

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Approximation algorithms (68W25)

Related Items (4)

Sharp spectral bounds of several graph parameters using eigenvector norms ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ Simple approximation algorithms for balanced MAX~2SAT ⋮ A spectral partitioning algorithm for maximum directed cut problem

This page was built for publication: Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning