مرجح للمطابقة عبر الإنترنت - الخوارزميات العشوائية

Question

دعونا نفكر في مشكلة مطابقة الحافة المرجحة عبر الإنترنت.

تصل القمم عبر الإنترنت والكشف عن جميع حوافها الحالية وأوزان الحافة $ w_e> 0 $ .الهدف هو زيادة وزن التطابقات.لا يمكن إضافة حافة فقط مرة واحدة ولا رجعة فيها للمطابقة.كما في كثير من الأحيان، نعتبر أساسا النظر في الإعداد من KVV.

من الواضح، أن أي خوارزمية حتمية لا يمكن أن تكون تنافسية ضد خصم غافل.نظرا لأن أي حافة جديدة يمكن أن يكون لها وزن كبير تعسفية.

هل يمكن أن تتحسن خوارزمية عشوائية عند هذه النتيجة؟

Answer 1

خوارزمية عشوائية لا يمكن أن تكون تنافسية ثابتة في النظام الأسوأ. يمكن العثور على دليل باستخدام مبدأ YAO هنا .