المطابقة الثنائية الموزونة

المطابقة الثنائية الموزونة (weighted bipartite matching) هي مسألة بحوث العمليات لإيجاد، في مخطّط ثنائي بمجموعتي رؤوس منفصلتين U وV حيث يحمل كلّ حرف ممكن (u,v) وزنًا، مجموعة الحواف ذات الوزن الإجمالي الأقصى (أو الأدنى)، بشرط ألّا يلمس أيّ رأس أكثر من حرف واحد. هي إطار المطابقة الأعمّ في التحسين التجميعي؛ الحالات الخاصّة: الحالة المربّعة المتوازنة (|U| = |V|) هي **مسألة التخصيص**، تُحَلّ بالخوارزمية المجرية (Kuhn 1955؛ Munkres 1957) في زمن متعدّد الحدود O(n³)؛ الحالة المستطيلة (|U| ≠ |V|) تُعالَج بتمديد رؤوس dummy؛ مطابقة الوزن الأقصى الأعمّ (حيث يُسمح برؤوس غير مُطابَقة في كلا الطرفين) لها عائلة خوارزمياتها. الخوارزميات: المطابقة بالوزن الأقصى متعدّدة الحدود (Edmonds 1965 وما بعد)؛ الحالة الكلاسيكية تُحلّ بالخوارزمية المجرية O(n³)، وLAP (Jonker-Volgenant 1987) أسرع عمليًا. التطبيقات الميدانية: تخصيص الأفراد-المهام، مطابقة العميل-الفنّي، توزيع الإعلانات، المطابقة الثنائية الفورية (#034)، مطابقة العطاءات-الحزم. Burkard وDell'Amico وMartello (2009) هو المرجع القياسي.