0.935-Approximation Randomized Algorithm for MAX 2SAT and Its Derandomization

概要

論文の詳細を見る
In this paper, we propose 0.935-approximation algorithm for MAX 2SAT. The approximation ratio is better than the previously known result by Zwick, which is equal to 0.93109. The algorithm solves the SDP relaxation problem proposed by Goemans and Williamson for the first time. We do not use the 'rotation' technique proposed by Feige and Goemans. We improve the approximation ratio by using hyperplane separation technique with skewed distribution function on the sphere. We introduce a class of skewed distribution functions defined on the 2-dimensional sphere satisfying that for any function in the class, we can design a skewed distribution functions on any dimensional sphere without decreasing the approximation ratio. We also searched and found a good distribution function defined on the 2-dimensional sphere numerically. And we propose the derandomized algorithm for the introduced distribution functions.
一般社団法人情報処理学会の論文
2001-11-27