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

DOI10.1137/S0097539797321481MaRDI QIDQ4268884zbMATH OpenOpenAlexFDO

Authors Howard 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

approximation algorithmMAX CUTsemidefinite programming

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1256761
• On the integrality ratio of semidefinite relaxations of MAX CUT
• On the optimality of the random hyperplane rounding technique for MAX CUT
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Cited in

(22)

• Affine reductions for LPs and SDPs
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• On the eigenvalues of Grassmann graphs, bilinear forms graphs and Hermitian forms graphs
• Eigenvalues of Cayley graphs
• Some observations on the smallest adjacency eigenvalue of a graph
• Semidefinite programming and eigenvalue bounds for the graph partition problem
• The maximum cut problem on blow-ups of multiprojective spaces
• 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
• Cuts for mixed 0-1 conic programming
• Constructing worst case instances for semidefinite programming based approximation algorithms
• Constructing worst case instances for semidefinite programming based approximation algorithms
• scientific article; zbMATH DE number 1256761 (Why is no real title available?)
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques
• On the integrality ratio of semidefinite relaxations of MAX CUT
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Unique games on the hypercube
• A review on quantum approximate optimization algorithm and its variants
• A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem
• Semidefinite programming and linear equations vs. homomorphism problems
• On the approximability of Max-Cut

This page was built for publication: How Good is the Goemans--Williamson MAX CUT Algorithm?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4268884)