scientific article; zbMATH DE number 2086914

MaRDI QIDQ4737518zbMATH OpenFDO

Authors Michael Lewin, Dror Livnat, Uri Zwick

Publication date 11 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2337/23370067.htm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

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

(36)

• Sums of squares based approximation algorithms for MAX-SAT
• Improved approximation for orienting mixed graphs
• NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
• On regularity of Max-CSPs and Min-CSPs
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Complexity issues in color-preserving graph embeddings
• Maximal and maximum transitive relation contained in a given binary relation
• Simple approximation algorithms for balanced MAX~2SAT
• Technical note: Assortment optimization with small consideration sets
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
• scientific article; zbMATH DE number 7758361 (Why is no real title available?)
• Lower bounds of functions on finite abelian groups
• Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• Complexity of approximating CSP with balance/hard constraints
• Hardness of approximation for knapsack problems
• scientific article; zbMATH DE number 7306863 (Why is no real title available?)
• Random MAX SAT, random MAX CUT, and their phase transitions
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• Approximation Algorithms for CSPs
• Semidefinite programming based approaches to the break minimization problem
• Oblivious algorithms for the maximum directed cut problem
• Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs
• Simultaneous approximation of multi-criteria submodular function maximization
• Computing better approximate pure Nash equilibria in cut games via semidefinite programming
• A spectral partitioning algorithm for maximum directed cut problem
• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• Constrained assortment optimization under the paired combinatorial logit model
• Optimal allocation in combinatorial auctions with quadratic utility functions
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Online submodular maximization with preemption
• Adapting local sequential algorithms to the distributed setting

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4737518)