¡Hola! me gustaría saber si el problema Balompié tiene una solución en tiempo polinomial o si se esperaba algún tipo de aproximación. Lo traté de pensar como un matching pero no encontré ninguna bipartición. Luego como una red de flujo para grafos generales pero no se me ocurrió nada que modele el problema tampoco. ¡Muchas gracias!
3 Me gusta
¡Hola!
No sé exactamente qué se esperaba para ese problema, si backtrackings podados y los casos eran generosos, o si estaba puesto como problema super-difícil, o si una mezcla de ambos. Como sea, existe un algoritmo polinomial para matching, pero es muy avanzado: https://en.wikipedia.org/wiki/Maximum_weight_matching
Podemos concluir que es un problema difícil, muy teórico 
5 Me gusta
Muchas gracias por responder Agus.
Aprovecho para decirte: ¡felicitaciones por tu canal de Youtube! es una idea fantástica, realmente explicás muy bien. Considero que va a ayudar a mucha gente que comparte el amor por las competencias, seguí adelante 
.
3 Me gusta