Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
1995/11/01 by Michel X. Goemans, David P. Williamson · 242 citations
Computer Science · Mathematics · Engineering · #Complexity and Algorithms in Graphs #Advanced Optimization Algorithms Research #Smart Parking Systems Research
paper · pdf · doi:10.1145/227683.227684
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\n 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\n 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\n cross-correlation vectors, with applications to phase retrieval and blind\n 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 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
- 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