文章基本信息

标题：Improved Approximation of MAX-CUT on Graphs of Bounded Degree
本地全文：下载
作者：Uriel Feige ; Marek Karpinski ; Michael Langberg 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We analyze the addition of a simple local improvement step to various known randomized approximation algorithms. Let 087856 denote the best approximation ratio currently known for the Max Cut problem on general graphs~\cite{GW95}. We consider a semidefinite relaxation of the Max Cut problem, round it using the random hyperplane rounding technique of (\cite{GW95}), and then add a local improvement step. We show that for graphs of degree at most , our algorithm achieves an approximation ratio of at least +, where 0 is a constant that depends only on . In particular, using computer assisted analysis, we show that for graphs of maximal degree 3, our algorithm obtains an approximation ratio of at least 0921, and for 3-regular graphs, the approximation ratio is at least 0924. We note that for the semidefinite relaxation of Max Cut used in~\cite{GW95}, the integrality gap is at least 10884 , even for 2-regular graphs.
关键词：Approximation Algorithms, Approximation Ratios, bounded degree graphs, Bounded MAX-CSP, Integrality Gap, Max-Cut, MAX-SAT, Random Hyperplanes, Semidefinite Relaxation, Triangle Constraints