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

Abstract

"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 diseñaron un m-algoritmo de aproximación aleatorio para max cut con m=0,87856... al cual en este trabajo llamaremos algoritmo G-W, este aprovecha la equivalencia de max cut con el problema de programación entera..."