How Good is the Goemans--Williamson MAX CUT Algorithm?
From MaRDI portal
Publication:4268884
DOI10.1137/S0097539797321481zbMath0942.90033OpenAlexW2093546055MaRDI QIDQ4268884
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
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
