Journal
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC
Volume 53, Issue 2, Pages 169-185Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jalgor.2004.06.001
Keywords
-
Ask authors/readers for more resources
We present an improved semidefinite programming based approximation algorithm for the MAX CUT problem in graphs of maximum degree at most 3. The approximation ratio of the new algorithm is at least 0.9326. This improves, and also somewhat simplifies, a result of Feige, Karpinski and Langberg. We also observe that results of Hopkins and Staton and of Bondy and Locke yield a simple combinatorial 4/5-approximation algorithm for the problem. Finally, we present a combinatorial 22/27-approximation algorithm for the MAX CUT problem for regular cubic graphs. (C) 2004 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available