الخوارزميات التقريبية لمركز واسييرستاين الكثيف مع القيم الشاذة

مركز واسييرستاين (WB) هو أحد المشكلات الأساسية في تحسين النقل الأمثل. بالنظر إلى مجموعة من التوزيعات، فإن الهدف من WB هو إيجاد توزيع جديد يقلل المسافة المتوسطة لواريستين بينها. تصبح المشكلة أكثر صعوبة إذا قمنا بتقييد الحل ليكون ''كثيفًا k''. في هذه الورقة، ندرس مشكلة WB الكثيفة مع القيم الشاذة، وهي حالة أكثر عملية حيث تحتوي البيانات الواقعية غالبًا على ضوضاء. لا يمكن توسيع خوارزميات WB الحالية مباشرة للتعامل مع الحالة التي تتضمن القيم الشاذة، ومن ثم فإن الحاجة ملحة لتطوير أفكار جديدة. أولاً، نستكشف العلاقة بين WB الكثيف مع القيم الشاذة ومشكلات التجميع (مع القيم الشاذة). بشكل خاص، نقترح طريقة LP قائمة على التجميع التي تنتج عامل تقريب ثابت لمشكلة WB الكثيفة مع القيم الشاذة. علاوة على ذلك، نستخدم تقنية الـ coreset لتحقيق عامل التقريب (1 +) لأي > 0، إذا كانت الأبعاد ليست مرتفعة. أخيرًا، نقوم بإجراء التجارب على خوارزمياتنا المقترحة ونوضح كفاءاتها في الممارسة العملية.