محور مقصوص: خوارزمية تجميع الارتباط لنماذج الحوسبة الديناميكية والمتوازية والمحلية

بالنظر إلى رسم بياني يحتوي على تسميات حواف إيجابية وسلبية، تهدف مشكلة تجميع الارتباط إلى تجميع العقد بطريقة تقلل من العدد الإجمالي للحواف الإيجابية بين المجموعات والسلبية داخل المجموعة. لهذه المشكلة العديد من التطبيقات في استخراج البيانات، خاصة في التعلم غير الخاضع للإشراف. مستوحين من انتشار الرسوم البيانية الكبيرة والبيانات المتغيرة باستمرار في التطبيقات الحديثة، ندرس تجميع الارتباط في إعدادات ديناميكية ومتوازية (MPC) ومحلية (LCA). نصمم نهجًا يُحسن تعقيدات وقت التشغيل القياسية في جميع هذه الإعدادات. على وجه الخصوص، نقدم أول خوارزمية ديناميكية كاملة تعمل في وقت متوقع ثابت مُقسط، دون أي اعتماد على حجم الرسم البياني. علاوة على ذلك، تتطابق خوارزميتنا بشكل أساسي مع ضمان الاقتراب من خوارزمية المحور الشهيرة.