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

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

Cites work

scientific article; zbMATH DE number 1261818 (Why is no real title available?)
scientific article; zbMATH DE number 739280 (Why is no real title available?)
scientific article; zbMATH DE number 1559516 (Why is no real title available?)
Bipartite Subgraphs and the Smallest Eigenvalue
Geometry of cuts and metrics
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
Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
Property testing and its connection to learning and approximation
Spherical rearrangements, subharmonic functions, and \(\ast\)-functions in \(n\)-space

Cited in

(30)

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
scientific article; zbMATH DE number 7561741 (Why is no real title available?)
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
scientific article; zbMATH DE number 1754595 (Why is no real title available?)
Comparison of metric spectral gaps
A novel formulation of the max-cut problem and related algorithm
Small bipartite subgraph polytopes
scientific article; zbMATH DE number 7378699 (Why is no real title available?)
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
The critical window for the classical Ramsey-Turán problem
Unique games on the hypercube
.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
Sherali-Adams strikes back
Sublinear algorithms for MAXCUT and correlation clustering

Describes a project that uses

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)