.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
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, 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
