How Good is the Goemans--Williamson MAX CUT Algorithm?

DOI10.1137/S0097539797321481zbMath0942.90033OpenAlexW2093546055MaRDI QIDQ4268884

Howard J. Karloff

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingapproximation algorithmMAX CUT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the optimality of the random hyperplane rounding technique for MAX CUT ⋮ Eigenvalues of Cayley graphs ⋮ Unnamed Item ⋮ The maximum cut problem on blow-ups of multiprojective spaces ⋮ Affine reductions for LPs and SDPs ⋮ Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques ⋮ Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation ⋮ A semidefinite programming based polyhedral cut and price approach for the maxcut problem ⋮ The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters ⋮ Some observations on the smallest adjacency eigenvalue of a graph ⋮ Cuts for mixed 0-1 conic programming ⋮ Semidefinite programming and eigenvalue bounds for the graph partition problem ⋮ On the eigenvalues of Grassmann graphs, bilinear forms graphs and Hermitian forms graphs