المشاركة العظمى في أنظمة المجموعات الوراثية

ننظر في مشكلة تخصيص مجموعة من العناصر غير القابلة للتجزئة بشكل عادل وفقًا لمعايير ضمان المشاركة العظمى. بشكل خاص، ندرس تقريب تخصيصات المشاركة العظمى تحت تقييمات أنظمة المجموعات الوراثية، حيث تستند كل دالة تقييم إلى المجموعات المستقلة من أنظمة المجموعات الوراثية الأساسية. باستخدام نهج المقسم الوحيد، نثبت وجود تخصيصات تقارب 1/2 من المشاركة العظمى، مما يحسن ضمان 11/30 الذي قدمه لي وفيتا. علاوة على ذلك، نثبت أن تخصيصات MMS التقريبية (2/3 +) ليست موجودة دائمًا في هذا النموذج لكل > 0، وهو تحسين من نتيجة لي ودنج الأخيرة 3/4 +. دليل وجودنا بنّاء، لكنه لا ينتج مباشرةً خوارزمية تقريبية ذات زمن كثير الحدود. ومع ذلك، نوضح أنه يمكن العثور على تخصيص MMS التقريبي 2/5 في زمن كثير الحدود، إذا توفرت أوراق التقييم. أخيرًا، نوضح أن نتائج وجودنا والتقريب تنتقل إلى مجموعة متنوعة من المشكلات ضمن التخصيص العادل المقيد، مما يحسن على النتائج الحالية في بعض هذه الإعدادات.