Outward rotations:a tool for rounding solutions of semidefinite programming relaxations,with applications to MAX CUT and other problems

摘要

We present a tool,outward rotations,for enhancing the performance of several semidefinite programming based approximation algorikthms.Using outward rotations,we obtain an approximation algorithm for MAX CUT that,in many interesting cases,performs better that the algorithm of Goemans and Williamson.We also obtain an improved approximation algorithm for MAXNAE-{3}-SAT.Finally,we provide some evidence that outward rotations can also be used to obtain improved approximation algorithms for MAX NAE-SAT and MXA SAT.