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

DOI10.1145/195058.195216zbMath1345.68274MaRDI QIDQ2817633

David P. Williamson, Michel X. Goemans

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

Mathematics Subject Classification ID

90C30: Nonlinear programming

68W25: Approximation algorithms

68W20: Randomized algorithms

Related Items

Energy Efficient Monitoring in Sensor Networks, Approximation of rank function and its application to the nearest low-rank correlation matrix, Constructing uniquely realizable graphs, Energy efficient monitoring in sensor networks, The real positive semidefinite completion problem for series-parallel graphs, Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem, Verifying exactness of relaxations for robust semi-definite programs by solving polynomial systems, Parameterizing above or below guaranteed values, A combinatorial algorithm for MAX CSP, Path optimization for graph partitioning problems, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality, On dependent randomized rounding algorithms, Approximability of maximum splitting of k-sets and some other Apx-complete problems, On approximation algorithms for the minimum satisfiability problem, Clique is hard to approximate within \(n^{1-\epsilon}\), Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, A randomized approximation scheme for metric MAX-CUT, Ellipsoidal bounds for uncertain linear equations and dynamical systems, Random sampling and approximation of MAX-CSPs, On a positive semidefinite relaxation of the cut polytope, Solving the max-cut problem using eigenvalues, A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming, Maximum renamable Horn sub-CNFs