Buenas noches,
Hoy vimos los conceptos de problema de optimización combinatoria junto con 5 ejemplos que estudiaremos durante el curso.
Luego definimos problema de NP-optimización combinatoria de clase NP-difícil, el concepto de algoritmo de aproximación y dos versiones de reducibilidad. La primera permite determinar si un problema de decisión pertenece a la clase de problemas NP-difíciles, y se llama reducibilidad de Karp. La segunda es una reducción que preserva el factor de aproximación.
Se recomienda resolver el ejercicio 2 para asegurarse dominar estos conceptos.
Cordiales saludos,
Pablo.