Glosario · approach
Emparejamiento Bipartito Ponderado
Problema de OR de encontrar, en un grafo bipartito con aristas con pesos, un emparejamiento de peso total máximo (o mínimo) entre dos conjuntos disjuntos de vértices.
Weighted Bipartite MatchingMaximum-Weight Bipartite Matching
El emparejamiento bipartito ponderado (weighted bipartite matching) es el problema de investigación operativa de encontrar, en un grafo bipartito con dos conjuntos disjuntos de vértices U y V en el que cada posible arista (u,v) lleva un peso, el conjunto de aristas con peso total máximo (o mínimo), sujeto a que ningún vértice toque más de una arista. Es el marco de emparejamiento más general en optimización combinatoria; casos especiales: el caso cuadrado y equilibrado (|U| = |V|) es el **problema de asignación**, resuelto por el algoritmo húngaro (Kuhn 1955; Munkres 1957) en tiempo polinómico O(n³); el caso rectangular (|U| ≠ |V|) se maneja con extensión por vértices dummy; el emparejamiento de peso máximo más general (con vértices sin emparejar permitidos a ambos lados) tiene su propia familia algorítmica. Algoritmos: el emparejamiento de peso máximo es polinómico (Edmonds 1965 y posteriores); el caso clásico de asignación se resuelve por el algoritmo húngaro O(n³), y LAP (Jonker-Volgenant 1987) es más rápido en la práctica. Aplicaciones de campo: asignación personal-tarea, emparejamiento cliente-técnico, colocación de anuncios, online bipartite matching (#034), emparejamiento puja-paquete. Burkard, Dell'Amico y Martello (2009) es la referencia canónica.
Örnek
Entre 10 trabajadores y 10 tareas, donde cada par (trabajador, tarea) tiene una puntuación competencia-duración, el emparejamiento bipartito ponderado devuelve la asignación uno-a-uno que maximiza la puntuación total; con el algoritmo húngaro O(n³) el óptimo está garantizado.