Glossario · approach
Matching Bipartito Pesato
Problema di ricerca operativa di trovare, in un grafo bipartito con archi pesati, un matching di peso totale massimo (o minimo) tra due insiemi disgiunti di vertici.
Weighted Bipartite MatchingMaximum-Weight Bipartite Matching
Il matching bipartito pesato (weighted bipartite matching) è il problema della ricerca operativa di trovare, in un grafo bipartito con due insiemi disgiunti di vertici U e V in cui ciascun arco possibile (u,v) ha un peso, l'insieme di archi con peso totale massimo (o minimo), con il vincolo che nessun vertice tocchi più di un arco. È il framework di matching più generale nell'ottimizzazione combinatoria; casi particolari: il caso quadrato e bilanciato (|U| = |V|) è il **problema di assegnazione**, risolto dal metodo ungherese (Kuhn 1955; Munkres 1957) in tempo polinomiale O(n³); il caso rettangolare (|U| ≠ |V|) si gestisce con estensione tramite vertici dummy; il matching di peso massimo più generale (in cui vertici non accoppiati su entrambi i lati sono ammessi) ha una propria famiglia di algoritmi. Algoritmi: il matching di peso massimo è polinomiale (Edmonds 1965 e seguenti); il caso classico di assegnazione si risolve col metodo ungherese O(n³), e LAP (Jonker-Volgenant 1987) è più veloce in pratica. Applicazioni: assegnazione personale-compito, abbinamento cliente-tecnico, posizionamento di annunci, online bipartite matching (#034), abbinamento offerta-pacchetto. Burkard, Dell'Amico e Martello (2009) è la referenza canonica.
Örnek
Tra 10 dipendenti e 10 compiti, dove ciascuna coppia (dipendente, compito) ha un punteggio competenza-durata, il matching bipartito pesato restituisce l'assegnazione uno-a-uno che massimizza il punteggio totale; con il metodo ungherese O(n³) l'ottimo è garantito.