On the optimality of the random hyperplane rounding technique for MAX CUT
From MaRDI portal
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
- Bipartite Subgraphs and the Smallest Eigenvalue
- Geometry of cuts and metrics
- How Good is the Goemans--Williamson MAX CUT Algorithm?
- 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?)
- 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
(43)- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- Robust optimality of Gaussian noise stability
- Light spanners for high dimensional norms via stochastic decompositions
- A novel formulation of the max-cut problem and related algorithm
- Least squares estimation in the monotone single index model
- Spherical basis functions and uniform distribution of points on spheres
- Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
- Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
- Spherical cap discrepancy of the diamond ensemble
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- SDP gaps and UGC-hardness for max-cut-gain
- On Khot’s unique games conjecture
- Approximating CSPs using LP relaxation
- Spectral bounds for the maximum cut problem
- scientific article; zbMATH DE number 1256761 (Why is no real title available?)
- scientific article; zbMATH DE number 1302192 (Why is no real title available?)
- How Good is the Goemans--Williamson MAX CUT Algorithm?
- scientific article; zbMATH DE number 1754595 (Why is no real title available?)
- Sublinear algorithms for MAXCUT and correlation clustering
- Light spanners for high dimensional norms via stochastic decompositions
- Sherali-adams strikes back
- scientific article; zbMATH DE number 7561741 (Why is no real title available?)
- Sherali-Adams strikes back
- Diameter bounded equal measure partitions of Ahlfors regular metric measure spaces
- On the integrality ratio of semidefinite relaxations of MAX CUT
- The critical window for the classical Ramsey-Turán problem
- One-bit sensing, discrepancy and Stolarsky's principle
- Comparison of metric spectral gaps
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Unique games on the hypercube
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- Small bipartite subgraph polytopes
- Estimation and convergence rates in the distributional single index model
- Geometric constructions for Ramsey-Turán theory
- Small-set expansion in the Johnson graph
- A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem
- Equal area partitions of the sphere with diameter bounds, via optimal transport
- Rates of convergence of the constrained least squares estimator in high-dimensional monotone single-index models
- On the pair correlation statistics for determinantal point processes on the sphere
- Improved parallel derandomization via finite automata with applications
- Triangles improve 0.878 approximation for Maxcut
- Tightness of a MaxCut lower bound via vector chromatic number
- Noise stability of functions with low influences: invariance and optimality
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)
