Resumen

Se propone un algoritmo heurístico basado en VNS para resolver los problemas Max 3-cut y Max 3-section. Estableciendo una estructura de vecindad del problema Max 3-cut, proponemos un algoritmo de búsqueda local y un algoritmo de búsqueda global de vecindad variable con dos pasos de búsqueda estocástica para obtener la solución global. Proporcionamos algunos resultados numéricos y comparaciones con el conocido algoritmo 0.836-approximate. Los resultados numéricos muestran que el algoritmo heurístico propuesto puede obtener eficientemente las soluciones de alta calidad y tiene el mejor rendimiento numérico que el algoritmo 0.836-aproximado para los problemas NP-Hard Max 3-cut y Max 3-section.

• Materias:Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:max, algoritmo aproximado, algoritmo heurístico, problemas de sección, mejor rendimiento numérico, algoritmo de búsqueda global, algoritmo de búsqueda local, pasos de búsqueda estocástica, corte, hard max
• Keywords:max, approximate algorithm, heuristic algorithm, section problems, better numerical performance, global search algorithm, local search algorithm, stochastic search steps, cut, hard max