scientific article; zbMATH DE number 2086914

zbMATH Open1049.90535MaRDI QIDQ4737518FDOQ4737518

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

Title of this publication is not available (Why is that?)

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

Mathematics Subject Classification ID

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

Cited In (36)

• Sums of squares based approximation algorithms for MAX-SAT
• NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
• Improved approximation for orienting mixed graphs
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• On regularity of Max-CSPs and Min-CSPs
• Complexity issues in color-preserving graph embeddings
• Technical note: Assortment optimization with small consideration sets
• Maximal and maximum transitive relation contained in a given binary relation
• Title not available (Why is that?)
• Simple approximation algorithms for balanced MAX~2SAT
• 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
• Title not available (Why is that?)
• Lower bounds of functions on finite abelian groups
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
• 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
• Title not available (Why is that?)
• Random MAX SAT, random MAX CUT, and their phase transitions
• Approximation Algorithms for CSPs
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• 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
• Constrained assortment optimization under the paired combinatorial logit model
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
• 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)