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