Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming Export

@article{goemans-williamson-jacm95, abstract = {We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions of expected value at least .87856 times the optimal value. These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation. This relaxation can be interpreted both as a semidefinite program and as an eigenvalue minimization problem. The best previously known approximation...}, author = {Goemans, Michel X. and Williamson, David P.}, citeulike-article-id = {1434204}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.9509}, journal = {J. Assoc. Comput. Mach.}, keywords = {approximation, maxcut}, pages = {1115--1145}, posted-at = {2008-09-05 03:17:12}, priority = {2}, title = {Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.9509}, volume = {42}, year = {1995} }

TY - JOUR ID - goemans-williamson-jacm95 L3 - citeulike-article-id:1434204 N2 - We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions of expected value at least .87856 times the optimal value. These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation. This relaxation can be interpreted both as a semidefinite program and as an eigenvalue minimization problem. The best previously known approximation... JF - J. Assoc. Comput. Mach. EP - 1145 TI - Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming VL - 42 SP - 1115 KW - approximation KW - maxcut AU - Goemans, Michel AU - Williamson, David PY - 1995/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.9509 ER -