تتطلب مشكلة الوسيط إيجاد سلسلة تقلل من المسافة المتوسطة من مجموعة معينة من السلاسل. تحت مقياس ليفينشتاين (أو مقياس تحرير)، تعتبر المشكلة صعبة من نوع NP حتى بالنسبة للسلاسل الثنائية. قمنا بابتكار نموذجين جديدين للبرمجة الخطية الصحيحة لهذه الحالة واختبرناهما ضد الصياغة الوحيدة التي نعلم عنها في الأدبيات. تشهد تجاربنا العددية على كفاءة النهج المقترح.
درس Arbib وآخرون (الخميس) هذا السؤال.