Se propuso un nuevo algoritmo para resolver el problema del corte máximo, que busca identificar el corte con el peso máximo en un grafo dado. Nuestra técnica se basa en el enfoque de paquetes, aplicado a una relajación semidefinida recién formulada. Esta investigación establece la convergencia teórica de nuestra técnica de aproximación y presenta los resultados numéricos obtenidos en varios grafos a gran escala de la biblioteca BiqMac, específicamente con 100, 250 y 500 nodos. El rendimiento resultante se comparó con el producido por dos métodos de aproximación alternativos basados en programación semidefinida, a saber, los solucionadores BiqMac y BiqBin, comparando el tiempo de CPU y el número de llamadas a funciones. El objetivo principal de este trabajo fue mejorar la escalabilidad y la eficiencia computacional en la resolución del problema del corte máximo, particularmente para instancias de grafos a gran escala. A pesar del desarrollo de numerosos algoritmos de aproximación, un desafío persistente radica en manejar efectivamente problemas con un gran número de restricciones. Nuestro algoritmo aborda esto integrando una nueva relajación semidefinida con un marco de optimización basado en paquetes, logrando una convergencia más rápida y menos llamadas a funciones. Estos avances marcan un paso significativo hacia adelante en la resolución eficiente de problemas de optimización combinatoria NP-duros.