Loading...
Please wait, while we are loading the content...
Similar Documents
Improved Approximation Algorithms for Maximum Cut and Satissability Problems Using Semideenite Programming
| Content Provider | Semantic Scholar |
|---|---|
| Author | Goemansy, Michel X. Williamsonz, David P. |
| Copyright Year | 1995 |
| Abstract | We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satissability (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 semideenite program and as an eigenvalue minimization problem. The best previously known approximation algorithms for these problems had performance guarantees of 1 2 for MAX CUT and 3 4 for MAX 2SAT. Slight extensions of our analysis lead to a .79607-approximation algorithm for the maximum directed cut problem (MAX DICUT) and a .758-approximation algorithm for MAX SAT, where the best previously known approximation algorithms had performance guarantees of 1 4 and 3 4 respectively. Our algorithm gives the rst substantial progress in approximating MAX CUT in nearly twenty years, and represents the rst use of semideenite programming in the design of approximation algorithms. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.duke.edu/courses/current/cps232/reading/10.1.1.3.9509.pdf |
| Alternate Webpage(s) | http://karush.rutgers.edu/~alizadeh/Sdppage/Goemans/maxcut.ps |
| Alternate Webpage(s) | http://dimacs.rutgers.edu/~dieter/Seminar/Papers/gw-maxcut.ps |
| Alternate Webpage(s) | http://www.almaden.ibm.com/cs/people/dpw/Cut/maxcut.ps |
| Alternate Webpage(s) | http://www.cs.duke.edu/courses/current/compsci532/reading/10.1.1.3.9509.pdf |
| Alternate Webpage(s) | http://www.cs.duke.edu/courses/cps230/fall12/reading/10.1.1.3.9509.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
