مسارات منفصلة مرفوعة مع تطبيق في تتبع كائنات متعددة

نقدّم امتدادًا لمشكلة المسارات المنفصلة يُدخل فيه حواف إضافية مُرفوعة (lifted) لتوفير معلومات أولية حول الاتصال بالمسارات. نُسمّي المشكلة التحسينية الناتجة بـ"مشكلة المسارات المنفصلة المُرفوعة". نُظهر أن هذه المشكلة صعبة NP من خلال التخفيض من مسألة تدفق البضائع المتعددة بأعداد صحيحة و3-SAT. ولتمكين التحسين العالمي العملي، نقترح عدة فئات من المتباينات الخطية التي تُنتج تخفيفًا خطيًا عالي الجودة. علاوةً على ذلك، نقترح خوارزميات فعّالة للفصل باستخدام طرق الأسطح المقطوعة (cutting plane) للفصل بين المتباينات الخطية المقترحة. تُعدّ مشكلة المسارات المنفصلة المُرفوعة نموذجًا طبيعيًا للتتبع متعدد الأجسام، وتوفر صيغة رياضية أنيقة للتفاعلات الزمنية الطويلة المدى. تساعد الحواف المرفوعة في منع تبديل الهوية (id switches) وإعادة تحديد الأشخاص. يحقق مُرَاقِب المسارات المنفصلة المُرفوعة تعيينات شبه مثالية بالنسبة للكشفات المدخلة، مما يُسهم في تحقيق أداء متفوّق على جميع المعايير الثلاثة الرئيسية في تحدي التتبع متعدد الأجسام (MOT)، مع تحسين ملحوظ مقارنة بأحدث التقنيات.