Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

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. Slightly improved results would appear in the full version of the paper.

REFERENCES

• 1: Piotr Berman , Marek Karpinski, On Some Tighter Inapproximability Results (Extended Abstract), Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.200-209, July 11-15, 1999
• 2: {BL86} J. A. Bondy and S. C. Locke. Largest bipartite subgraphs in triangle-free graphs with maximum degree three. Journal of Graph Theory, 10:477-504, 1986.
• 3: {FKL00} U. Feige, M. Karpinski, and M. Langberg. Improved approximation of Max-Cut on graphs of bounded degree. Technical report, E-CCC Report number TR00-043, 2000.
• 4: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 5: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 6: Johan Håstad, On bounded occurrence constraint satisfaction, Information Processing Letters, v.74 n.1-2, p.1-6, April 2000 [doi>10.1016/S0020-0190(00)00032-6]
• 7: {HS82} G. Hopkins and W. Staton. Extremal bipartite subgraphs of cubic triangle-free graphs. Journal of Graph Theory, 6:115-121, 1982.
• 8: Eran Halperin , Uri Zwick, Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs, Journal of Algorithms, v.40 n.2, p.184-211, August 2001 [doi>10.1006/jagm.2001.1162]
• 9: Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.406, October 19-22, 1997
• 10: Luca Trevisan , Gregory B. Sorkin , Madhu Sudan , David P. Williamson, Gadgets, Approximation, and Linear Programming, SIAM Journal on Computing, v.29 n.6, p.2074-2097, April 2000 [doi>10.1137/S0097539797328847]
• 11: Uri Zwick, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.679-687, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301431]
• 12: Uri Zwick, Computer assisted proof of optimal approximability results, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.496-505, January 06-08, 2002, San Francisco, California