Sea una gráfica con la función de peso . El problema de max-cut es encontrar: If la función de peso no es negativa (es decir, w (e) \ geq 0 para todas las e \ en E ), entonces hay muchas aproximaciones de 2 extremadamente simples para max-cut. Por ejemplo, podemos:G=(V,E,w)G = (V, E,...