Extensión del Lema Local de Lovász y su aplicación en problemas minimax 0-1

Abstract

El estudio tiene como objetivo formular e implementar una extensión del Lema Local de Lovász para optimizar la resolución de problemas de optimización combinatoria de tipo minimax mediante el desarrollo de algoritmos computacionales, en el marco de una investigación teórico-aplicada con validación experimental estructurada en fases de revisión conceptual, implementación, optimización y validación; se desarrolló un entorno computacional en Python empleando bibliotecas especializadas para el redondeo aleatorio y la resolución de relajaciones lineales, evaluándose el desempeño del método en conjuntos de datos sintéticos y reales correspondientes a redes de malla inalámbricas con diversas topologías y condiciones de interferencia; los resultados evidenciaron que la propuesta alcanza un equilibrio favorable entre calidad de solución y eficiencia computacional, logrando reducciones en los tiempos de ejecución de entre 12 y 726 veces respecto a métodos exactos, con brechas de aproximación inferiores al 7% frente a la relajación lineal; se concluye que la extensión del Lema Local de Lovász constituye una herramienta robusta y viable para abordar problemas NP-difíciles de programación entera, permitiendo obtener soluciones competitivas en tiempos significativamente menores, lo cual resulta relevante para aplicaciones en tiempo real.