Bosque de Recolecta de Premios con Penalizaciones Submodulares: Mejora de la Aproximación

Los problemas de bosque restringido forman una clase de problemas de grafos donde deben satisfacerse requisitos específicos de conectividad para ciertos cortes dentro del grafo seleccionando el conjunto de bordes de costo mínimo. La versión de recolección de premios de estos problemas introduce flexibilidad al permitir el pago de penalizaciones para ignorar algunos requisitos de conectividad. Goemans y Williamson introdujeron una técnica general y desarrollaron un algoritmo de aproximación 2 para problemas de bosque restringido. Además, Sharma, Swamy y Williamson ampliaron este trabajo desarrollando un algoritmo de aproximación 2.54 para la versión de recolección de premios de estos problemas. Motivados por la generalidad de su marco, que incluye problemas como árboles de Steiner, bosques de Steiner y sus variantes, continuamos con la exploración. Presentamos una mejora significativa al lograr un algoritmo de aproximación 2 para este modelo general, igualando el factor de aproximación de los problemas de bosque restringido.