Aproximación de problemas combinatorios con optimización semidefinida y redondeo aleatorio

"Max cut es el problema de hallar el corte máximo sobre los vértices de un grafo en el cual se le ha asignado un valor no negativo y racional a cada arista. Este problema es NP-Hard y por tanto no existe un algoritmo que lo resuelva en tiempo polinomial a menos que P = NP. Goemans y Williamson...