Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Klein, Philip N. Lu, Hsueh-I. |
| Description | The best known approximation algorithm for graph MAX CUT, due to Goemans and Williamson, first finds the optimal solution a semidefinite 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 semidefinite program. Solving these semidefinite 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. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing |
| File Format | |
| Language | English |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Efficient Approximation Algorithm Graph Max Cut Optimal Solution Graph Coloring Graph Cut Semidefinite Program Arising Max Cut Semidefinite Program Approximation Algorithm Known Approximation Algorithm |
| Content Type | Text |
| Resource Type | Article |
