.879-approximation algorithms for MAX CUT and MAX 2SAT
From MaRDI portal
Publication:2817633
DOI10.1145/195058.195216zbMath1345.68274OpenAlexW2080905757MaRDI 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
Related Items (51)
Ellipsoidal bounds for uncertain linear equations and dynamical systems ⋮ Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat} ⋮ Random sampling and approximation of MAX-CSPs ⋮ On a positive semidefinite relaxation of the cut polytope ⋮ Approximation of Constraint Satisfaction via local search ⋮ Approximability of maximum splitting of k-sets and some other Apx-complete problems ⋮ On approximation algorithms for the minimum satisfiability problem ⋮ Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ On dependent randomized rounding algorithms ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ Solving the max-cut problem using eigenvalues ⋮ A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming ⋮ Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Approximation of rank function and its application to the nearest low-rank correlation matrix ⋮ Constructing uniquely realizable graphs ⋮ Semidefinite programming and its applications to NP problems ⋮ Convex Maximization via Adjustable Robust Optimization ⋮ A geometric approach to betweenness ⋮ Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs ⋮ Impact of graph structures for QAOA on maxcut ⋮ Energy efficient monitoring in sensor networks ⋮ Solving MaxCut with quantum imaginary time evolution ⋮ Solving the maximum duo-preservation string mapping problem with linear programming ⋮ Finding the maximum cut by the greedy algorithm ⋮ Maximum renamable Horn sub-CNFs ⋮ The Convex Hull of a Quadratic Constraint over a Polytope ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ The real positive semidefinite completion problem for series-parallel graphs ⋮ Verifying exactness of relaxations for robust semi-definite programs by solving polynomial systems ⋮ Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION ⋮ Coloring bipartite hypergraphs ⋮ Improved randomized approximation algorithms for lot-sizing problems ⋮ An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity ⋮ An approximation algorithm for alphabet indexing problem ⋮ An approximation algorithm for MAX 3-SAT ⋮ Unnamed Item ⋮ Max-bisections of \(H\)-free graphs ⋮ Parameterizing above or below guaranteed values ⋮ Energy Efficient Monitoring in Sensor Networks ⋮ A combinatorial algorithm for MAX CSP ⋮ Path optimization for graph partitioning problems ⋮ Solving quadratic (0,1)-problems by semidefinite programs and cutting planes ⋮ Eigenvector-based identification of bipartite subgraphs ⋮ Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality ⋮ The legacy of Jean Bourgain in geometric functional analysis ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ On dependent randomized rounding algorithms ⋮ Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem ⋮ A randomized approximation scheme for metric MAX-CUT ⋮ Better approximation algorithms for influence maximization in online social networks
This page was built for publication: .879-approximation algorithms for MAX CUT and MAX 2SAT
