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

DOI10.1002/RSA.10036zbMATH Open1005.90052OpenAlexW1985476702MaRDI QIDQ4537629FDOQ4537629

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

Recommendations

• A randomized approximation scheme for metric MAX-CUT
• On the approximability of Max-Cut
• MAX-CUT has a randomized approximation scheme in dense graphs
• Randomized heuristics for the Max-Cut problem
• Near-optimal approximation algorithm for simultaneous Max-Cut
• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• A gradient-based randomised heuristic for the maximum cut problem
• On the maximal cut in a random hypergraph
• Randomized rounding for the largest simplex problem

zbMATH Keywords

semidefinite programming relaxationMAX CUT

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Property testing and its connection to learning and approximation
• On the cut polytope
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Geometry of cuts and metrics
• Title not available (Why is that?)
• Spherical rearrangements, subharmonic functions, and \(\ast\)-functions in \(n\)-space
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
• How Good is the Goemans--Williamson MAX CUT Algorithm?
• Bipartite Subgraphs and the Smallest Eigenvalue
• Title not available (Why is that?)

Cited In (29)

• SDP gaps and UGC-hardness for max-cut-gain
• Spectral bounds for the maximum cut problem
• Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Title not available (Why is that?)
• On the integrality ratio of semidefinite relaxations of MAX CUT
• One-bit sensing, discrepancy and Stolarsky's principle
• On Khot’s unique games conjecture
• Least squares estimation in the monotone single index model
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Noise stability of functions with low influences: invariance and optimality
• Title not available (Why is that?)
• Comparison of metric spectral gaps
• A novel formulation of the max-cut problem and related algorithm
• Title not available (Why is that?)
• Small bipartite subgraph polytopes
• Spherical cap discrepancy of the diamond ensemble
• Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
• Approximating CSPs using LP relaxation
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
• Spherical basis functions and uniform distribution of points on spheres
• Robust optimality of Gaussian noise stability
• Estimation and convergence rates in the distributional single index model
• Unique games on the hypercube
• The critical window for the classical Ramsey-Turán problem
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Light spanners for high dimensional norms via stochastic decompositions
• Diameter bounded equal measure partitions of Ahlfors regular metric measure spaces
• Sublinear algorithms for MAXCUT and correlation clustering

Uses Software

• Outward rotations

This page was built for publication: On the optimality of the random hyperplane rounding technique for MAX CUT

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