On the optimality of the random hyperplane rounding technique for MAX CUT

DOI10.1002/rsa.10036zbMath1005.90052OpenAlexW1985476702MaRDI QIDQ4537629

Gideon Schechtman, Uriel Feige

Publication date: 1 July 2002

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10036

zbMATH Keywords

semidefinite programming relaxationMAX CUT

Mathematics Subject Classification ID

Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Related Items

Approximating CSPs Using LP Relaxation, Spherical cap discrepancy of the diamond ensemble, Unnamed Item, Small bipartite subgraph polytopes, Spherical basis functions and uniform distribution of points on spheres, Unnamed Item, One-bit sensing, discrepancy and Stolarsky's principle, Sublinear Algorithms for MAXCUT and Correlation Clustering, Comparison of Metric Spectral Gaps, Diameter bounded equal measure partitions of Ahlfors regular metric measure spaces, The critical window for the classical Ramsey-Turán problem, Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation, Noise stability of functions with low influences: invariance and optimality, Robust optimality of Gaussian noise stability, Unnamed Item, A novel formulation of the max-cut problem and related algorithm, Spectral bounds for the maximum cut problem, On Khot’s unique games conjecture, Least squares estimation in the monotone single index model, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁, Light spanners for high dimensional norms via stochastic decompositions, Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spherical rearrangements, subharmonic functions, and \(\ast\)-functions in \(n\)-space
• Outward rotations
• Property testing and its connection to learning and approximation
• How Good is the Goemans--Williamson MAX CUT Algorithm?
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the cut polytope
• Bipartite Subgraphs and the Smallest Eigenvalue
• Geometry of cuts and metrics