Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems
From MaRDI portal
(Redirected from Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems)
Recommendations
- NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- scientific article; zbMATH DE number 956857
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs
Cited in
(48)- Simple approximation algorithms for balanced MAX~2SAT
- Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
- On regularity of Max-CSPs and Min-CSPs
- Hardness of approximation for knapsack problems
- Oblivious algorithms for the maximum directed cut problem
- Semidefinite programming based approaches to the break minimization problem
- Improved approximation for orienting mixed graphs
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- Optimal allocation in combinatorial auctions with quadratic utility functions
- Complexity of approximating CSP with balance/hard constraints
- Maximal and maximum transitive relation contained in a given binary relation
- A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
- Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
- Random MAX SAT, random MAX CUT, and their phase transitions
- Simultaneous approximation of multi-criteria submodular function maximization
- Online submodular maximization with preemption
- Approximation Algorithms for CSPs
- Constrained assortment optimization under the paired combinatorial logit model
- Adapting local sequential algorithms to the distributed setting
- scientific article; zbMATH DE number 7561584 (Why is no real title available?)
- Technical note: Assortment optimization with small consideration sets
- Generating weighted MAX-2-SAT instances with frustrated loops: an RBM case study
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- scientific article; zbMATH DE number 956857 (Why is no real title available?)
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- A spectral partitioning algorithm for maximum directed cut problem
- scientific article; zbMATH DE number 7758361 (Why is no real title available?)
- A new upper bound for Max-2-SAT: A graph-theoretic approach
- Computing better approximate pure Nash equilibria in cut games via semidefinite programming
- Lower bounds of functions on finite abelian groups
- Separating coverage and submodular: maximization subject to a cardinality constraint
- Some results on approximability of minimum sum vertex cover
- On the mysteries of MAX NAE-SAT
- Algorithmic persuasion with evidence
- Fault tolerant max-cut
- Separating \textsc{max} 2-and, \textsc{max di-cut}, and \textsc{max cut}
- Approximability of longest run subsequence and complementary minimization problems
- Maximum and- vs. even-SAT
- Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT
- A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
- Complexity issues in color-preserving graph embeddings
- Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
- Sums of squares based approximation algorithms for MAX-SAT
This page was built for publication: Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4737518)
