Loading...
Please wait, while we are loading the content...
Similar Documents
Eecient Approximation Algorithms for Semideenite Programs Arising from Max Cut and Coloring Eecient Approximation Algorithms for Semideenite Programs Arising from Max Cut and Coloring
| Content Provider | Semantic Scholar |
|---|---|
| Author | Klein, Philip N. |
| Copyright Year | 1996 |
| Abstract | The best known approximation algorithm for graph MAX CUT, due to Goemans and Williamson, rst nds the optimal solution a semideenite program and then derives a graph cut from that solution. Building on this result, Karger, Motwani, and Sudan gave an approximation algorithm for graph coloring that also involves solving a semideenite program. Solving these semideenite programs using known methods (ellipsoid, interior-point), though polynomial-time, is quite expensive. We show how they can be approximately solved in ~ O(nm) time for graphs with n nodes and m edges. |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |