.878-approximation algorithms for MAX CUT and MAX 2SAT

DOI10.1145/195058.195216zbMATH Open1345.68274OpenAlexW2080905757MaRDI QIDQ2817633FDOQ2817633

Authors: Michel X. Goemans, David P. Williamson 

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195216

Recommendations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• scientific article; zbMATH DE number 2086914
• NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
• Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations
• On the optimality of the random hyperplane rounding technique for MAX CUT

Mathematics Subject Classification ID

Randomized algorithms (68W20) Nonlinear programming (90C30) Approximation algorithms (68W25)

Cited In (71)

• Title not available (Why is that?)
• Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
• Solving MaxCut with quantum imaginary time evolution
• A semidefinite approach for the single row facility layout problem
• Multiscale semidefinite programming approach to positioning problems with pairwise structure
• Approximation of Constraint Satisfaction via local search
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
• An optimal-storage approach to semidefinite programming using approximate complementarity
• Constructing uniquely realizable graphs
• SDP gaps and UGC-hardness for max-cut-gain
• The legacy of Jean Bourgain in geometric functional analysis
• Near-optimal approximation algorithm for simultaneous Max-Cut
• The Maximum k-Colorable Subgraph Problem and Related Problems
• Title not available (Why is that?)
• NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
• Energy efficient monitoring in sensor networks
• STACS 2005
• Eigenvector-based identification of bipartite subgraphs
• A geometric approach to betweenness
• Ellipsoidal bounds for uncertain linear equations and dynamical systems
• Solving the max-cut problem using eigenvalues
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Approximation algorithms for MAX RES CUT with limited unbalanced constraints
• Impact of graph structures for QAOA on maxcut
• Max cut and the smallest eigenvalue
• On the approximability of Max-Cut
• Parameterizing above or below guaranteed values
• An approximation algorithm for alphabet indexing problem
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
• The convex hull of a quadratic constraint over a polytope
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• On dependent randomized rounding algorithms
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Improved randomized approximation algorithms for lot-sizing problems
• Random sampling and approximation of MAX-CSPs
• Maximum renamable Horn sub-CNFs
• Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations
• An approximation algorithm for MAX 3-SAT
• Title not available (Why is that?)
• Max-bisections of \(H\)-free graphs
• On approximation algorithms for the minimum satisfiability problem
• On computational capabilities of Ising machines based on nonlinear oscillators
• Path optimization for graph partitioning problems
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• On dependent randomized rounding algorithms
• The real positive semidefinite completion problem for series-parallel graphs
• Improved approximation of Max-Cut on graphs of bounded degree
• Verifying exactness of relaxations for robust semi-definite programs by solving polynomial systems
• A combinatorial algorithm for MAX CSP
• On the advantage over a random assignment
• Better approximation algorithms for influence maximization in online social networks
• Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Semidefinite programming and its applications to NP problems
• Energy Efficient Monitoring in Sensor Networks
• Convex Maximization via Adjustable Robust Optimization
• Coloring bipartite hypergraphs
• The expected relative error of the polyhedral approximation of the max- cut problem
• On a positive semidefinite relaxation of the cut polytope
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• A randomized approximation scheme for metric MAX-CUT
• Solving the maximum duo-preservation string mapping problem with linear programming
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Gadgets, Approximation, and Linear Programming
• Finding the maximum cut by the greedy algorithm
• Approximation of rank function and its application to the nearest low-rank correlation matrix

This page was built for publication: .878-approximation algorithms for MAX CUT and MAX 2SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817633)