Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
1995/11/01 by Michel X. Goemans, David P. Williamson · 3,701 citations
Computer Science · Engineering · Mathematics · Medicine · #Advanced Optimization Algorithms Research #Algorithm #Artificial intelligence #Center (category theory) #Citation #Complexity and Algorithms in Graphs #Computer science #IBM #Library science #Mathematical optimization #Mathematics #Medicine #Physics #Research center #Satisfiability #Semidefinite programming #Smart Parking Systems Research #Watson
paper · pdf · doi:10.1145/227683.227684
published in Journal of the ACM 42(6), 1115-1145 (Association for Computing Machinery)
openalex publication_date 1995/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Abstract
We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions of expected value at least .87856 times the optimal value. These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation. This relaxation can be interpreted both as a semidefinite program and as an eigenvalue minimization problem. The best previously known approximation algorithms for these problems had perfc~rmance guarantees of ~for MAX CUT and ~for MAX 2SAT. Slight extensions of our analysis lead to a .79607-approximation algorithm for the maximum directed cut problem (MAX DICUT) and a .758-approximation algorithm for MAX SAT, where the best previously known approxim ation algorithms had performance guarantees of ~and ~, respectively. Our algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and represents the first use of :semidefinite programming in the design of approximation algorithms.
Cited by
- Nonconvex optimization methods for ground states in disordered continuous-spin models
- New results for MaxCut in HH‐free graphs
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Semidefinite programming relaxations for semialgebraic problems
- Efficiently Simulable Pauli Correlation Encoding
- Exact Nonnegative Matrix Factorization via Cone-Ray Witnesses: Certificates, a One-Sided Solver, and a Findability Phase Transition
- A Curvature-Aware Rank-Adaptive Distributed Augmented-Lagrangian Solver for Large-Scale SDPs
- Physics-Informed Learning of Effective Error Processes from Limited Noisy Transmon Measurements for Robust QAOA Reliability
- Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization
- The Quantum Optimization Benchmarking Library
- Semidefinite Programming Bounds on Fractional Cut-Cover and Maximum 2-SAT for Highly Regular Graphs
- Playing Games with Approximation Algorithms
- Computational Methods for Single-Particle Cryo-EM
- An FPT Algorithm for Max-Cut Parameterized by Crossing Number
- Quantum Algorithms for Fixed Qubit Architectures
- A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
- In Defense of MinHash Over SimHash
- Efficient Continuous Relaxations for Dense CRF
- A Low-Rank Rounding Heuristic for Semidefinite Relaxation of Hydro Unit Commitment Problems
- Constrained Submodular Maximization via a Non-symmetric Technique
- Using Negative Curvature in Solving Nonlinear Programs
- Benchmarking Lie-Algebraic Pretraining and Non-Variational QWOA for the MaxCut Problem
- A Newton-bracketing method for a simple conic optimization problem
- Semidefinite and Spectral Relaxations for Multi-Label Classification
- Majority is Stablest : Discrete and SoS
- Blind Identification of ARX Models with Piecewise Constant Inputs
- Approximating Max-Cut under Graph-MSO Constraints
- Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models
- Quantum Alternating Direction Method of Multipliers for Semidefinite Programming
- A Model Predictive Control-Inspired Quantum Algorithm
- Enhanced Distributed Variational Quantum Eigensolver for Large-Scale MaxCut Problem
- Incorporating rank-free coupling and external field via an incoherent modulated spatial photonic Ising machine
- A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees
- Lovász theta and Shearer lower bounds on Quantum Max Cut
- Block-Recurrent Dynamics in Vision Transformers
- Variational matrix product states for combinatorial optimization
- Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
- A 0.8395-approximation algorithm for the EPR problem
- Speeding up the Goemans-Williamson randomized procedure by difference-of-convex optimization
- Security and Privacy Issues in Deep Learning
- Exact and Stable Recovery of Rotations for Robust Synchronization
- Constraint-oriented biased quantum search for linear constrained combinatorial optimization problems
- MAX BISECTION might be harder to approximate than MAX CUT
- Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
- Classifying Approximation Algorithms: Understanding the APX Complexity Class
- A quantum-classical hybrid branch & bound algorithm
- Frustration indices of signed subcubic graphs
- SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver
- Phase Recovery, MaxCut and Complex Semidefinite Programming
- Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
- The Unique Games Conjecture with Entangled Provers is False
- Convex Relaxations for Subset Selection
- Efficient Balanced Treatment Assignments for Experimentation
- From Laplacian-to-Adjacency Matrix for Continuous Spins on Graphs
- Verification of Sequential Convex Programming for Parametric Non-convex Optimization
- Nearly tight bounds for MaxCut in hypergraphs
- An Optimal Algorithm for Online Unconstrained Submodular Maximization
- Hesse's Redemption: Efficient Convex Polynomial Programming
- Nodal Count for Orthogonally Invariant Ensembles
- Projected Subgradient Ascent for Convex Maximization
- GFORS: GPU-Accelerated First-Order Method with Randomized Sampling for Binary Integer Programs
- Empirical Studies on Quantum Optimization for Software Engineering: A Systematic Analysis
- FlowQ-Net: A Generative Framework for Automated Quantum Circuit Design
- A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming
- Face Structure in Partial Facial Reduction of Semidefinite Relaxations of Binary Programs
- A Semidefinite Relaxation for Air Traffic Flow Scheduling
- The minimax risk of truncated series estimators for symmetric convex polytopes
- Relaxations for inference in restricted Boltzmann machines
- Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities
- A Primal Approach to Facial Reduction for SDP Relaxations of Combinatorial Optimization Problems
- Semidefinite Relaxation of Quadratic Optimization Problems
- Phase Retrieval with Application to Optical Imaging: A contemporary overview
- Almost Optimal Intervention Sets for Causal Discovery
- 2-Coloring Cycles in One Round
- New results for MaxCut in H-free graphs
- Exactness in SDP relaxations of QCQPs: Theory and applications
- Extended Formulations for Online Linear Bandit Optimization
- Learning Graphs with Monotone Topology Properties and Multiple Connected Components
- An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization
- Monotone and near-monotone network structure (part I)
- Distributed Hierarchical GPU Parameter Server for Massive Scale Deep Learning Ads Systems
- Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs
- Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics
- Robust Discriminative Clustering with Sparse Regularizers
- Stable Camera Motion Estimation Using Convex Programming
- Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization
- A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond
- Quadratic Convergence of a Projection Method for a Plane Curve Feasibility Problem
- Universal energy-space localization and stable quantum phases against time-dependent perturbations
- Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems
- Best Arm Identification in Graphical Bilinear Bandits
- Nine lower bound conjectures on streaming approximation algorithms for CSPs
- 2-Bit Random Projections, NonLinear Estimators, and Approximate Near Neighbor Search
- Distributionally Robust Removal of Malicious Nodes from Networks
- On Symmetric and Asymmetric LSHs for Inner Product Search
- Semidefinite Programming and Nash Equilibria in Bimatrix Games
- Worst-Case Analysis for Randomly Collected Data
- Exponential Speed-ups for Structured Goemans-Williamson relaxations via Quantum Gibbs States and Pauli Sparsity
- Quantum-enhanced Computer Vision: Going Beyond Classical Algorithms
- Optimizing fermionic Hamiltonians with classical interactions
- H1B-KV: Hybrid One-Bit Caches for Memory-Efficient Large Language Model Inference
- Streaming Max-Cut in General Metrics
- Most tensor problems are NP-hard
- Vector Trifference
- The quantum smooth label cover problem is undecidable
- A Conditional Gradient-Based Augmented Lagrangian Framework
- A Hardware Accelerator for the Goemans-Williamson Algorithm
- Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
- Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
- Tight bounds for judicious 3-partitions of graphs
- No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
- Lower bounds on the size of semidefinite programming relaxations
- Simulating Quantum Correlations with Finite Communication
- Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
- Oblivious Algorithms for the Maximum Directed Cut Problem
- Sensitivity Analysis of Submodular Function Maximization
- A Scalable Lift-and-Project Differentiable Approach For the Maximum Cut Problem
- Robust Group Synchronization via Cycle-Edge Message Passing
- Convex Optimization without Projection Steps
- Sketching approximations and LP approximations for finite CSPs are related
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning
- Conic programming: infeasibility certificates and projective geometry
- Classical and Quantum Heuristics for the Binary Paint Shop Problem
- Выпуклая оптимизация
- Conic optimization techniques yield sufficient conditions for set-completely positive matrix completion under arrowhead specification pattern
- Warm-Starting PCE for Traveling Salesman Problem
- Beating the Minimax Rate of Active Learning with Prior Knowledge
- Fast implementation for semidefinite programs with positive matrix completion
- The maximum cut problem on blow-ups of multiprojective spaces
- Convex relaxations of structured matrix factorizations
- Joint User Grouping and Linear Virtual Beamforming: Complexity, Algorithms and Approximation Bounds
- Transversal polynomial of r-fold covers
- Quantum Supremacy through the Quantum Approximate Optimization Algorithm
- Notes on Randomized Algorithms
- Interval Superposition Arithmetic
- Quantum Speed-ups for Semidefinite Programming
- Low Rank Approximation with Entrywise ℓ1-Norm Error
- Quantization Algorithms for Random Fourier Features
- Subspace Variational Quantum Simulation: Fidelity Lower Bounds as Measures of Training Success
- ADMM for Multiaffine Constrained Optimization
- A Unified Framework for Structured Graph Learning via Spectral Constraints
- Max Cut and the Smallest Eigenvalue
- Use of MAX-CUT for Ramsey Arrowing of Triangles
- Learning Coverage Functions and Private Release of Marginals
- From small eigenvalues to large cuts, and Chowla's cosine problem
- Learning Combinatorial Optimization Algorithms over Graphs
- Improved Analysis of a Max Cut Algorithm Based on Spectral Partitioning
- A Continuous Energy Ising Machine Leveraging Difference-of-Convex Programming
- An O(|E|)-linear Model for the MaxCut Problem
- A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
- A Hybrid Algorithm for Convex Semidefinite Optimization
- Genuine multipartite entanglement verification with convolutional neural networks
- Prospects and challenges of quantum finance
- Submodularization for Quadratic Pseudo-Boolean Optimization
- How Well Do Local Algorithms Solve Semidefinite Programs?
- The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
- Enhancing Balanced Graph Edge Partition with Effective Local Search
- Quantum-Guided Cluster Algorithms for Combinatorial Optimization
- Phase Retrieval with Application to Optical Imaging
- Efficient Approximation Algorithms for Adaptive Target Profit Maximization
- Non-monotone submodular maximization under matroid and knapsack constraints
- Delay and Power Tradeoff with Consideration of Caching Capabilities in Dense Wireless Networks
- Tomography-assisted noisy quantum circuit simulator using matrix product density operators
- Clustering a Mixture of Gaussians with Unknown Covariance
- Reconstruction of signals from their autocorrelation and cross-correlation vectors, with applications to phase retrieval and blind channel estimation
- Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT
- Inference in Graphical Models via Semidefinite Programming Hierarchies
- Quantum Approximate Multi-Objective Optimization
- Unique Games with Entangled Provers are Easy
- Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity
- On the practically interesting instances of MAXCUT
- A Faster Interior Point Method for Semidefinite Programming
- Hierarchical Clustering: New Bounds and Objective
- On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments
- Hybrid Precoding for Multi-Group Multicasting in mmWave Systems
- A comprehensive benchmark of an Ising machine on the Max-Cut problem
- Sampling (noisy) quantum circuits through randomized rounding
- A Near Maximum Likelihood Decoding Algorithm for MIMO Systems Based on Semi-Definite Programming
- Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
- Optimization of Lyapunov Invariants in Verification of Software Systems\n (Extended Version)
- A Paradigm for Channel Assignment and Data Migration in Distributed Systems
- Sparse similarity-preserving hashing
- Deterministic Blind Rendezvous in Cognitive Radio Networks
- Sketching semidefinite programs for faster clustering
- Approximation Algorithms for Semi-random Graph Partitioning Problems
- Applying Practice to Theory
- A Restricted Dual Peaceman-Rachford Splitting Method for QAP
- Bounded Independence Fools Degree-2 Threshold Functions
- Experimental performance of graph neural networks on random instances of max-cut
- Symmetric Grothendieck inequality
- Learning-to-learn non-convex piecewise-Lipschitz functions
- Maximin Optimization for Binary Regression
- On Quadratic Programming with a Ratio Objective
- Active Community Detection with Maximal Expected Model Change
- Overcoming barriers to scalability in variational quantum Monte Carlo
- Unsupervised authorship attribution
- Subsampling Algorithms for Semidefinite Programming
- Noisy intermediate-scale quantum (NISQ) algorithms
- Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
- Random MAX SAT, Random MAX CUT, and Their Phase Transitions
- Binarizing Physics-Inspired GNNs for Combinatorial Optimization
- Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
- Coding for Random Projections
- Sum of Squares Lower Bounds from Pairwise Independence
- An Exact Solver for Submodular Knapsack Problems
- Tensor-Tensor Products, Group Representations, and Semidefinite Programming
- Beyond the MaxCut problem in H-free graphs
- Max-Cut with Multiple Cardinality Constraints
- On approximate quantum error correction for symmetric noise
- Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians
- Semidefinite Programming in Timetabling and Mutual-Exclusion Scheduling
- On the Learnability of Deep Random Networks
- Prize-collecting Network Design on Planar Graphs
- Problems and results on judicious partitions
- A multidimensional maximum bisection problem
- A Faster Algorithm for Max Cut in Dense Graphs
- A Semidefinite Approach to the Ki Cover Problem
- Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs
- An Optimization-Free Recursive QAOA for the Binary Paint Shop Problem
- Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
- Beyond-mean-field fluctuations for the solution of constraint satisfaction problems
- Optimal Pricing in Networks with Externalities
- Using the Eigenvalue Relaxation for Binary Least-Squares Estimation Problems
- Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
- A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
- Graph Neural Networks for Maximum Constraint Satisfaction
- Power-optimal, stabilized entangling gate between trapped-ion qubits
- Stiefel optimization is NP-hard
- Clustering on the Edge: Learning Structure in Graphs
- Breaking the n1.5 Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
- Degree Bounds for Polynomial Verification of the Matrix Cube Problem
- On the Efficiency of Influence-and-Exploit Strategies for Revenue\n Maximization under Positive Externalities
- Noise stability of functions with low influences: invariance and optimality
- Factorization norms and an inverse theorem for MaxCut
- A sub-constant improvement in approximating the positive semidefinite Grothendieck problem
- Efficient Semidefinite Branch-and-Cut for MAP-MRF Inference
- A Decomposition Augmented Lagrangian Method for Low-rank Semidefinite Programming
- Fast entropy-regularized SDP relaxations for permutation synchronization
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- The Lasserre Hierarchy in Almost Diagonal Form
- Low-rank Matrix Optimization Using Polynomial-filtered Subspace Extraction
- Towards an O(√[3]log n)-Approximation Algorithm for \sc Balanced Separator
- Optimal Sparse Output Feedback Control Design: a Rank Constrained Optimization Approach
- Range-Doppler Sidelobe Suppression for Pulsed Radar Based on Golay Complementary Codes
- A Convex Relaxation for Weakly Supervised Classifiers
- Tell me something my friends do not know: Diversity maximization in social networks
- A Goemans-Williamson type algorithm for identifying subcohorts in clinical trials
- Semidefinite approximation for mixed binary quadratically constrained quadratic programs
- Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)
- Adam assisted Fully informed Particle Swarm Optimization ( Adam-FIPSO ) based Parameter Prediction for the Quantum Approximate Optimization Algorithm (QAOA)
- Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
- Max-Cut Parameterized Above the Edwards-Erdős Bound
- Multiple Illumination Phaseless Super-Resolution (MIPS) with Applications To Phaseless DOA Estimation and Diffraction Imaging
- Design of Spectrally Shaped Binary Sequences via Randomized Convex Relaxation
- Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism
- Efficient Approximate Solutions to Mutual Information Based Global Feature Selection
- A Characterization of Approximation Resistance
- Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
- A Graph Decomposition motivated by the Geometry of Randomized Rounding
- Maximal and maximum transitive relation contained in a given binary relation
- Elastic Index Selection for Label-Hybrid AKNN Search
- Bridging Quantum Chemistry and MaxCut: Classical Performance Guarantees and Quantum Algorithms for the Hartree-Fock Method
- An Enhanced SDR based Global Algorithm for Nonconvex Complex Quadratic Programs with Signal Processing Applications
- An approximation algorithm for approximation rank
- Testing the Nullspace Property using Semidefinite Programming
- A Triangle Algorithm for Semidefinite Version of Convex Hull Membership Problem
- Approximate maximum entropy principles via Goemans-Williamson with applications to provable variational methods
- Better Gap-Hamming Lower Bounds via Better Round Elimination
- Angular Synchronization by Eigenvectors and Semidefinite Programming
- Depth Optimized Ansatz Circuit in QAOA for Max-Cut
- Enhancing low-rank solutions in semidefinite relaxations of Boolean quadratic problems
- Reversible Action Design for Combinatorial Optimization with Reinforcement Learning
- Tightness of a new and enhanced semidefinite relaxation for MIMO detection
- Improved Approximations for Hard Graph Problems using Predictions
- On the low-rank approach for semidefinite programs arising in synchronization and community detection
- Asymmetric Minwise Hashing
- Max-Bisections of graphs without even cycles
- Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
- Learning for Dynamic Combinatorial Optimization without Training Data
- Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
- Sums of Squares and Sparse Semidefinite Programming
- A loop Quantum Approximate Optimization Algorithm with Hamiltonian updating
- STORM: Foundations of End-to-End Empirical Risk Minimization on the Edge
- A Framework for Stochastic Differentiable Programming
- Submodular Function Maximization over Distributive and Integer Lattices
- Optimal quantisation of probability measures using maximum mean discrepancy
- A Quantum Annealing Approach to Reduce Covid-19 Spread on College Campuses
- Improved Parameterized Algorithms for Constraint Satisfaction
- Quantum computation: Algorithms and Applications
- The status of the P versus NP problem
- On the Equivalence of SDP Feasibility and a Convex Hull Relaxation for System of Quadratic Equations
- Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
- Dropping Convexity for Faster Semi-definite Optimization
- Unique Games on the Hypercube
- A Comparison of Relaxations of Multiset Cannonical Correlation Analysis\n and Applications
- Approximation of the weighted maximin dispersion problem over Lp-ball: SDP relaxation is misleading
- A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut
- PSSE Redux: Convex Relaxation, Decentralized, Robust, and Dynamic Approaches
- Complexity analysis of the Controlled Loosening-up (CLuP) algorithm
- Shrink-Wrapping trajectories for Linear Programming
- The Curse and Blessing of Not-All-Equal in k-Satisfiability
- Approximation Complexity of Max-Cut on Power Law Graphs
- Phase-only signal reconstruction by MagnitudeCut
- The threshold for SDP-refutation of random regular NAE-3SAT
- Multireference Alignment using Semidefinite Programming
- Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT
- A Subsampling Theorem for Constraint Satisfaction Problems with Large Arity
- Coordinate Descent Algorithms for Phase Retrieval
- Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment
- Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
- The equivalence between doubly nonnegative relaxation and semidefinite relaxation for binary quadratic programming problems
- Exact Spin Elimination in Ising Hamiltonians and Energy-Based Machine Learning
- Hamming Compressed Sensing
- Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
- Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups
- On exactness of SDP relaxation for the maximum cut problem
- Binary Sequence Set Design for Interferer Rejection in Multi-Branch Modulation
- A Two-Phase Exact Algorithm for MAX-SAT and Weighted MAX-SAT Problems
- On Assessing the Quantum Advantage for MaxCut Provided by Quantum Neural Network Ansätze
- Sublinear Maximum Inner Product Search using Concomitants of Extreme Order Statistics
- The Diversity Order of the Semidefinite Relaxation Detector
- Balanced Combinations of Solutions in Multi-Objective Optimization
- Certifying Quantum Optimization and Circuit Cutting by Using Quantum-Classical Moment Duality
- Starting CLuP with polytope relaxation
- Approximating the cut-norm via Grothendieck's inequality
- Cryptography in a Quantum World
- Complexity Aspects of Fundamental Questions in Polynomial Optimization
- Learning to Learn with Quantum Optimization via Quantum Neural Networks
- Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube
- Maximizing Quadratic Programs: Extending Grothendieck's Inequality
- Convex Optimization: Algorithms and Complexity
- On the Approximation of Submodular Functions
- Mathematical and Algorithmic Analysis of Network and Biological Data
- Near-optimal approximation algorithm for simultaneous Max-Cut
- Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube
- Strongly Convex Maximization via the Frank-Wolfe Algorithm with the Kurdyka-Łojasiewicz Inequality
- Relations between average case complexity and approximation complexity
- Maximizing Non-monotone Submodular Set Functions Subject to Different\n Constraints: Combined Algorithms
- Bounding Probability of Small Deviation: A Fourth Moment Approach
- Random Features for Grassmannian Kernels
- The Nature of Computation
- Warm-Starting QAOA with XY Mixers: A Novel Approach for Quantum-Enhanced Vehicle Routing Optimization
- On the volume of the elliptope and related metric polytopes
- A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
- Investigation of Automated Design of Quantum Circuits for Imaginary Time Evolution Methods Using Deep Reinforcement Learning
- A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
- Proof verification and the hardness of approximation problems
- Kernels and Regularization on Graphs
- On the asymptotic minimum number of monochromatic 3-term arithmetic progressions
- Hyperbolic geometry of complex networks
- A polynomial-time algorithm to find an equitable home–away assignment
- Balanced max 2-sat might not be the hardest
- Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
- Lagrangian Relaxation
- Sign Stable Random Projections for Large-Scale Learning
- Every Permutation CSP of arity 3 is Approximation Resistant
- A Geometric Approach to Betweenness
- A rewriting system for convex optimization problems
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
- On the Degree Automatability of Sum-of-Squares Proofs
- Expander flows, geometric embeddings and graph partitioning
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- A new point of NP-hardness for unique games
- Optimal algorithms and inapproximability results for every CSP?
- Some topics in analysis of boolean functions
- Nonlinear Integer Programming
- Concave Quadratic Cuts for Mixed-Integer Quadratic Problems
- SDP-based bounds for graph partition via extended ADMM
- Path Matters: Industrial Data Meet Quantum Optimization
- Sign Stable Projections, Sign Cauchy Projections and Chi-Square Kernels
- Active Robust Learning
- Forbidden minor characterizations for low-rank optimal solutions to\n semidefinite programs over the elliptope
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- On Minimal Valid Inequalities for Mixed Integer Conic Programs
- Low-rank semidefinite programming for the MAX2SAT problem
- Gadgets, Approximation, and Linear Programming
- Finite Quantum Tomography and Semidefinite Programming
- Modularity-maximizing graph communities via mathematical programming
- Solving the max-3-cut problem using synchronized dissipative networks
- Detecting the solution space of vertex cover by mutual determinations and backbones
- Certified Defenses against Adversarial Examples
- Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
- Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
- Reducing the number of time delays in coupled dynamical systems
- Relaxations of the Satisfiability Problem Using Semidefinite Programming
- Detection of core–periphery structure in networks using spectral methods and geodesic paths
- On maximization of quadratic form over intersection of ellipsoids with common center
- Relaxations of Quadratic Programs in Operator Theory and System Analysis
- Grothendieck‐Type Inequalities in Combinatorial Optimization
- Grothendieck’s Theorem, past and present
- Approximate graph coloring by semidefinite programming
- Approximating the Cut-Norm via Grothendieck's Inequality
- Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Sampling-based Quantum Optimization Algorithm with Quantum Relaxation
- Transferring linearly fixed QAOA angles: performance and real device results
- Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem
- Max-Cut graph-driven quantum circuit design for planar spin glasses
- Standardization of Multi-Objective QUBOs
- Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
- An Adaptive Weighted QITE-VQE Algorithm for Combinatorial Optimization Problems
- Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
- IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
- Max Cut
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Similarity estimation techniques from rounding algorithms
- Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
- Simplicial Faces of the Set of Correlation Matrices
- A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
- QPanda3: A High-Performance Software-Hardware Collaborative Framework for Large-Scale Quantum-Classical Computing Integration
- Cut (graph theory) [wikipedia]
- Maximum cut [wikipedia]
- Unique games conjecture [wikipedia]
- Improved IBD detection using incomplete haplotype information. [europepmc]
- SDhaP: haplotype assembly for diploids and polyploids via semi-definite programming. [europepmc]
- Reconstructing a SuperGeneTree minimizing reconciliation. [europepmc]
- Matching-range-constrained real-time loop closure detection with CNNs features. [europepmc]
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up. [europepmc]
- A single shot coherent Ising machine based on a network of injection-locked multicore fiber lasers. [europepmc]
- Graph Neural Networks for Maximum Constraint Satisfaction. [europepmc]
- Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles. [europepmc]
- Mean field approximation for solving QUBO problems. [europepmc]
- A tree search algorithm towards solving Ising formulated combinatorial optimization problems. [europepmc]
- Large-scale coherent Ising machine based on optoelectronic parametric oscillator. [europepmc]
- Multidimensional hyperspin machine. [europepmc]
- SLfRank: Shinnar-Le-Roux Pulse Design With Reduced Energy and Accurate Phase Profiles Using Rank Factorization. [europepmc]
- Bifurcation behaviors shape how continuous physical dynamics solves discrete Ising optimization. [europepmc]
- Noisecut: a python package for noise-tolerant classification of binary data using prior knowledge integration and max-cut solutions. [europepmc]
- Fundamental limits to multi-functional and tunable nanophotonic response. [europepmc]
- Computing with oscillators from theoretical underpinnings to applications and demonstrators. [europepmc]
- Towards large-scale quantum optimization solvers with few qubits. [europepmc]
- Solving the maximum cut problem using Harris Hawk Optimization algorithm. [europepmc]
- ON-OFF neuromorphic ISING machines using Fowler-Nordheim annealers. [europepmc]
- MaxComp: Predicting single-cell chromatin compartments from 3D chromosome structures. [europepmc]
- Quantum approximate multi-objective optimization. [europepmc]
- Entanglement-assisted variational algorithm for discrete optimization problems. [europepmc]
- SUANPAN: scalable photonic linear vector machine. [europepmc]
- Hybrid Computational Modeling with Multi-Level Validation Identifies TK1–VIM as a Robust Therapeutic Pair in Triple-Negative Breast Cancer [europepmc]
Related