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

No abstract is available for this paper.

• Publication year

  2002

• Venue

  Random Struct. Algorithms

• Publication date

  2002-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/rsa.10036
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Geometry of cuts and metrics

  2009cited by this paper
• Improved approximation of Max-Cut on graphs of bounded degree

  2002cited by this paper
• Some optimal inapproximability results

  2001influential reference
• Bipartite Subgraphs and the Smallest Eigenvalue

  2000influential reference
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems

  1999cited by this paper
• Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example

  1999cited by this paper
• Improved Approximation Algorithms for Maximum Cut and Satissability Problems Using Semideenite Programming

  1997cited by this paper
• GEOMETRY OF SETS AND MEASURES IN EUCLIDEAN SPACES FRACTALS AND RECTIFIABILITY

  1996cited by this paper
• Property testing and its connection to learning and approximation

  1996cited by this paper
• How good is the Goemans-Williamson MAX CUT algorithm?

  1996cited by this paper
• Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability

  1995cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• Geometry of sets and measures in Euclidean spaces

  1995cited by this paper
• Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT

  1995cited by this paper
• Derandomizing semidefinite programming based approximation algorithms

  1995cited by this paper
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper
• Surveys in Combinatorics, 1989: On the method of bounded differences

  1989cited by this paper
• On the cut polytope

  1986cited by this paper
• Asymptotic Theory Of Finite Dimensional Normed Spaces

  1986cited by this paper
• Spherical rearrangements, subharmonic functions, and $\ast$-functions in $n$-space

  1976cited by this paper
• Probability inequalities for sum of bounded random variables

  1963cited by this paper

• MAX BISECTION might be harder to approximate than MAX CUT

  2025cites this paper
• A primal-dual extension of the Goemans–Williamson algorithm for the weighted fractional cut-covering problem

  2025cites this paper
• Warm-start adaptive-bias quantum approximate optimization algorithm

  2025cites this paper
• Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes

  2025cites this paper
• Triangles Improve 0.878 Approximation for Maxcut

  2025cites this paper
• On the pair correlation statistics for determinantal point processes on the sphere

  2025cites this paper
• Small Set Expansion in the Johnson Graph

  2025cites this paper
• The applicability of equal area partitions of the unit sphere

  2024cites this paper
• A Quantum Unique Games Conjecture

  2024cites this paper
• Weak to Strong Learning from Aggregate Labels

  2024influential citation
• Clique density vs blowups

  2024cites this paper
• Improved Parallel Derandomization via Finite Automata with Applications

  2024cites this paper
• Quadratic Memory Is Necessary for Optimal Query Complexity in Convex Optimization: Center of Mass Is Pareto Optimal

  2024cites this paper
• Graph with any rational density and no rich subsets of linear size

  2024cites this paper
• Prompting a Pretrained Transformer Can Be a Universal Approximator

  2024cites this paper
• Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs

  2024cites this paper
• Rates of convergence of the constrained least squares estimator in high-dimensional monotone single-index models

  2024cites this paper
• Equal area partitions of the sphere with diameter bounds, via optimal transport

  2023influential citation
• Efficiently Solving the Max-cut Problem via a Quantum Qubit Rotation Algorithm

  2023cites this paper
• Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal

  2023cites this paper
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

  2023cites this paper
• Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents

  2023cites this paper
• Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes

  2023cites this paper
• A Primal-Dual Extension of the Goemans-Williamson Algorithm for the Weighted Fractional Cut-Covering Problem

  2023cites this paper
• Estimation and convergence rates in the distributional single index model

  2023influential citation
• Combinatorial Optimization via the Sum of Squares Hierarchy

  2022cites this paper
• Learning in Stackelberg Games with Non-myopic Agents

  2022cites this paper
• An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs

  2022cites this paper
• Constraint Satisfaction Problems Lecture Notes

  2022cites this paper
• An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms

  2022cites this paper
• Exponential Decay of Intersection Volume With Applications on List-Decodability and Gilbert-Varshamov Type Bound

  2021cites this paper
• Testing thresholds for high-dimensional sparse random geometric graphs

  2021cites this paper
• Geometric constructions for Ramsey–Turán theory

  2021cites this paper
• Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes

  2020cites this paper
• An Approximation Algorithm for Maximizing Product Modularity

  2020cites this paper
• A novel formulation of the max-cut problem and related algorithm

  2020cites this paper
• Symmetric Grothendieck inequality

  2020influential citation
• Random path in negatively curved manifolds

  2020cites this paper
• A Fast Binary Quadratic Programming Solver Based on Stochastic Neighborhood Search

  2020influential citation
• A Non-Convex Optimization Approach to Correlation Clustering

  2019cites this paper
• Sum-of-Squares Optimization and the Sparsity Structure of Equiangular Tight Frames

  2019cites this paper
• Statistical physics approaches to unique games

  2019cites this paper
• Spherical Cap Discrepancy of the Diamond Ensemble

  2019cites this paper
• Connections between structured tight frames and sum-of-squares optimization

  2019cites this paper
• Krivine diffusions attain the Goemans-Williamson approximation ratio

  2019cites this paper
• The SDP value for random two-eigenvalue CSPs

  2019cites this paper
• Learning to Round for Discrete Labeling Problems

  2018cites this paper
• High-dimensional estimation via sum-of-squares proofs

  2018cites this paper
• Light Spanners for High Dimensional Norms via Stochastic Decompositions

  2018cites this paper
• Algorithms above the noise floor

  2018cites this paper
• Sublinear Algorithms for MAXCUT and Correlation Clustering

  2018influential citation
• A Semidefinite Formulation of the Shifting Load Management

  2018cites this paper
• PR ] 2 2 Fe b 20 13 Robust Optimality of Gaussian Noise Stability

  2017influential citation
• Однобитовые измерения, дискрепанс и принцип Столярского

  2017cites this paper
• High-dimensional similarity search and sketching: algorithms and hardness

  2017cites this paper
• One-bit sensing, discrepancy and Stolarsky's principle

  2017cites this paper
• Least squares estimation in the monotone single index model

  2016cites this paper
• Hardness of Approximation

  2016cites this paper
• Matrix Completion with Noisy Side Information

  2015cites this paper
• Analysis of Boolean functions

  2015cites this paper
• One Bit Sensing, Discrepancy, and Stolarsky Principle

  2015cites this paper
• Practical and Optimal LSH for Angular Distance

  2015cites this paper
• Diameter Bounded Equal Measure Partitions of Ahlfors Regular Metric Measure Spaces

  2015cites this paper
• One Bit Sensing, Discrepancy, and Stolarsky Principle

  2015cites this paper
• Berry-Esseen bounds for weighted averages of Poisson avoidance functionals

  2015cites this paper
• Approximating CSPs Using LP Relaxation

  2015cites this paper
• Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing

  2015cites this paper
• Semidefinite Programming Part 2

  2015cites this paper
• Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts

  2014cites this paper
• The critical window for the classical Ramsey-Turán problem

  2014influential citation
• Clustering and Resource Allocation for Dense Femtocells in a Two-Tier Cellular OFDMA Network

  2014cites this paper
• Tight Hardness of the Non-commutative Grothendieck Problem

  2014cites this paper
• Discrepancy, separation and Riesz energy of finite point sets on compact connected Riemannian manifolds

  2014cites this paper
• Unique Games on the Hypercube

  2014cites this paper
• Sparse signal processing: subspace clustering and system identification

  2014cites this paper
• Analysis of Boolean Functions

  2014cites this paper
• Sum of Squares Upper Bounds, Lower Bounds, and Open Questions

  2014cites this paper
• Social choice, computational complexity, Gaussian geometry, and Boolean functions

  2014cites this paper
• A characterization of strong approximation resistance

  2013cites this paper
• A Characterization of Approximation Resistance

  2013cites this paper
• Robust Subspace Clustering via Thresholding

  2013cites this paper
• Connectivity of Random High Dimensional Geometric Graphs

  2013cites this paper
• Comparison of Metric Spectral Gaps

  2013cites this paper
• To Sharon and to my parents

  2013influential citation
• Noisy subspace clustering via thresholding

  2013cites this paper
• Isoperimetry and noise sensitivity in Gaussian space

  2013cites this paper
• A gradient-based randomised heuristic for the maximum cut problem

  2012influential citation
• The critical window for the classical Ramsey-Turán problem

  2012influential citation
• On Khot’s unique games conjecture

  2012cites this paper
• A hybridization between memetic algorithm and semidefinite relaxation for the max-cut problem

  2012cites this paper
• Graph densification

  2012cites this paper
• Approximation Algorithms and Semidefinite Programming

  2012cites this paper
• Robust Optimality of Gaussian Noise Stability

  2012influential citation
• 3 Problem Definition

  2011cites this paper
• Rounding Semidefinite Programming Hierarchies via Global Correlation

  2011cites this paper
• The Design of Approximation Algorithms

  2011cites this paper
• Grothendieck Inequalities, Nonlocal Games and Optimization

  2011cites this paper
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack

  2010cites this paper
• Small bipartite subgraph polytopes

  2010cites this paper
• The Approximability of Learning and Constraint Satisfaction Problems

  2010influential citation