Múltiples decodificadores para resolver el problema de corte multidireccional con la metaheurística MP-BRKGA

En el Problema de Corte Multidireccional (MCP) queremos encontrar un recorte de costo mínimo que separe k terminales. Este problema es una versión NP-Hard del clásico problema de recorte mínimo, y surge en aplicaciones en áreas como la computación distribuida y la segmentación de imágenes. En este trabajo presentamos una variedad de decodificadores que utilizan diferentes enfoques en conjunto con la metaheurística MP-BRKGA para encontrar buenas soluciones para MCP. Estos decodificadores pueden adaptarse a otras metaheurísticas o utilizarse de forma independiente. Llevamos a cabo un análisis experimental detallado de nuestros decodificadores, demostrando que dos de ellos son capaces de lograr soluciones muy cercanas al valor óptimo de forma rápida y consistente.